堆

堆用于动态求取极值。

给予二叉堆实现

可以直接使用 stl 里面的 make_heap, push_heap, pop_heap, sort_heap 算法。

二叉堆就是一颗特殊的完全二叉树。对于小顶堆来说，父节点的权值不大于儿子的权值。

操作：下沉 + 上浮

class Heap {
  vector<int> data;
  int size;

public:
  Heap() : data({0}), size(0) {}

  void Push(int val) {
    data.push_back(val);
    ShiftUp(data.size() - 1);
    size++;
  }

  int Pop() {
    if (data.size() <= 1) {
      throw overflow_error("Data size");
    }
    int res = data[1];
    swap(*(data.begin() + 1), *(data.end() - 1));
    data.erase(data.end() - 1);
    size--;
    ShiftDown(1);
    return res;
  }

private:
  void ShiftDown(int index) {
    int temp = data[index];
    while ((index << 1) <= size) {
      // 左: 2*i 右:2*i+1
      int child = index << 1;
      if (child != size && data[child + 1] < data[child]) {
        // 使用右节点
        child++;
      }
      if (temp > data[child]) {
        dathead = new DListNode();
    tail = new DListNode();a[index] = data[child];
        index = child;
      } else {
        break;
      }
    }
    data[index] = temp; // swap
  }

  void ShiftUp(int index) {
    int temp = data[index];

    while ((index >> 1) > 0) {
      if (temp < data[index >> 1]) {
        data[index] = data[index >> 1];
        index = index >> 1;
      } else
        break;
    }
    data[index] = temp;
  }
};

Reference

1. 力扣加加: https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/heap