堆(heap) 是一种满足特定条件的完全二叉树。

• 完全二叉树（最底层节点靠左填充，其他层节点填满）
• 根节点称为堆顶，底层最靠右的节点称为堆底。
• 小顶堆的堆顶是最小的，大顶堆的堆顶是最大的。

堆的常用操作

// 初始化
priority_queue<vector<int>, greater<int>> minHeap; // 小顶堆，greater索引越大值越大。因此数组左边的堆顶是小的。
priority_queue<vector<int>, less<int>> maxHeap; // 大顶堆

maxHeap.push(1);
int peek = maxHeap.top();

maxHead.pop();

int size = maxHeap.size();
bool isEmpty = maxHeap.empty();

// 列表建堆
vector<int> input{1, 2, 3, 4, 5};

priority_queue<int, vector<int>, greater<int>> minHeap(input.begin(), input.end());

堆的实现

完全二叉树非常适合用数组表示，因此一般采用数组存储堆。

// 左孩子
int left(int i) {
	return 2*i + 1;
};

// 右孩子
int right(int i) {
  return 2*i + 1;
} 

// 父节点
int parent(int i) {
  (i - 1)/2;
}

// 访问堆顶元素
int peek() {
  return maxHeap[0];
}

元素入堆

对于给定元素，首先添加到堆底。添加以后，需要修复堆低节点到根节点的路径上所有的节点，该过程也称为自底向上堆化(sift up heapify)，时间复杂度为 $\log n$

void push(int val) {
  maxHeap.push_back(val);
  siftUp(size( - 1));
}

void siftUp(int i) {
  while (true) {
   int p = parent(i);
   if (p < 0 || maxHeap[i] <= maxHeap[p])
     break;
  }
  
  swap(maxHeap[i], maxHeap[p]);
  i = p;
}

元素出堆

堆顶元素如果直接删除，会让二叉树所有节点的索引都发生变化。为了减少元素索引的变化，采用以下步骤：

1. 交换堆顶和堆底元素。
2. 删除交换后的堆底元素。
3. 从根节点开始堆化(sift down)。

void pop() {
  if (isEmpty()) {
    throw out_of_range("empty")；
  }
  
  swqp(maxHeap[0], maxHeap[size - 1]);
  maxHeap.pop_back();
  siftDown(0);
}

void siftDown(int i) {
  while (true) {
    itn l = left(i), r = right(i), ma = i;
    if (l < size() && maxHeap[l] > maxHeap[ma]) ma = l;
    if (r < size() && maxHeap[r] > maxHeap[ma]) ma = r;
    
    if (ma == i) break;
    
    swap(maxHeap[i], maxHeap[ma]);
  }
}

建堆操作

由于叶子节点没有子节点，它们天然就是合法子堆，因此从最后一个父节点开始向堆顶遍历建堆。

MaxHeap(vector<int> nums) {
  maxHeap = nums;
  for (int i = parrent(size() - 1); i >= 0; --i) siftDown(i);
}