堆、priority_queue

堆（heap）

• 概念

  堆是一颗有着特殊性质的完全二叉树。对于树的每个结点，如果存在子树，那么该结点的权值大于等于（或者小于等于）子树中所有结点的权值

  如果根结点的权值大于等于子树的权值，称为大根堆；反之称为小根堆

  

• 堆的存储

  由于堆是一颗完全二叉树，故堆可以使用一个数组来存储（顺序存储）。顺序存储时，利用满二叉树的特性来计算父子结点关系

  注：

  • 存储虽然简单，但题目不会这么好心。一般给我们的是一组树，按照这组树还原成二叉树后，并不是堆结构
  • 我们有两种做法：用数组存下这组树，再调整成堆；或者创建一个堆，把这组树插入到堆中

• 练习（判断堆）

  

  注：图5不是一颗完全二叉树，故不是堆

堆的核心操作

• 概念

  堆中的所有运算，比如建堆、插入或删除元素，都是基于堆的两个核心操作实现的：

  • 向上调整算法
  • 向下调整算法

• 堆的常用存储结构

  如果将满二叉树，按照层序遍历的过程编号，那么

  结点 \(i\) 的左孩子编号：为 \(2i\)

  结点 \(i\) 的右孩子编号：为 \(2i + 1\)

  结点 \(i\) 的双亲编号：\(i/2\)

  注：若以 0 开始编号，则

  结点 \(i\) 的左孩子编号：为 \(2(i + 1) - 1=2i+1\)

  结点 \(i\) 的右孩子编号：为 \(2(i + 1) + 1 - 1 = 2i + 2\)

  结点 \(i\) 的双亲编号：\((i + 1)/2-1\)

• 向上调整算法（siftUp）

  向上调整算法，用于向堆中插入元素

  当堆中新来一个元素，放在末尾时，从这个结点开始逐渐向上调整（将该点与父结点的权值作比较，若比父节点大，则交换）。重复比较操作，直到小于等于父节点的权值，或换到根结点为止

  时间复杂度为 \(O(log(N))\)

• 向下调整算法（heapify）

  向下调整算法，用于删除堆顶元素，或者堆排序中的建堆操作

  向下调整，就是从这个结点开始，逐渐向下调整。找出左右孩子中权值最大的那个，如果该点的权值比权值大的孩子小，就交换。重复比较交换操作，直到该点比两个孩子结点的权值都大，或者换到叶子结点为止

  时间复杂度为 \(O(N)\)

  一般都是先把堆最后一个元素和目标结点交换，再对该点进行向下调整算法，则达到删除堆元素的目的

堆的模拟实现（大根堆）

• 代码实现

  #include <iostream>
  
  using namespace std;
  
  const int N = 1e6 + 10;
  int n, heap[N];
  
  // 向上调整算法
  void up(int child) {
      int parent = child / 2;
      while (parent >= 1 && heap[child] > heap[parent]) {
          swap(heap[child], heap[parent]);
          child = parent;
          parent = child / 2;
      }
  }
  
  // 向下调整算法
  void down(int parent) {
      int left_child = parent * 2;
  
      // 若左孩子不存在，则右孩子必定不存在
      while (left_child <= n) {
          int right_child = left_child + 1;
          int max_of_child = left_child;
          if (right_child < n && heap[right_child] > heap[left_child]) {
              max_of_child = right_child;
          }
          if (heap[parent] >= heap[max_of_child]) {
              return;
          }
          swap(heap[parent], heap[max_of_child]);
          parent = max_of_child;
          left_child = parent * 2;
      }
  }
  
  // 插入元素
  void push(int data) {
      heap[++n] = data;
      up(n);
  }
  
  // 删除堆顶元素（前提堆有元素）
  void pop() {
      swap(heap[1], heap[n]); // 交换到堆末尾
      n--; // 删除堆尾
      down(1);
  }
  
  // 查询堆顶元素（前提堆有元素）
  int top() {
      return heap[1];
  }
  
  // 堆的大小
  int size() {
      return n;
  }
  
  int main() {
      // 建堆
      int a[10] = {1, 41, 23, 10, 11, 2, -1, 99, 14, 0};
      for (int i = 0; i < 10; ++i) {
          push(a[i]);
      }
  
      while (size()) {
          cout << top() << " ";
          pop();
      }
  
      return 0;
  }