Heap

堆（Heap）

[TOC]

堆的基本概念

二叉堆的基本概念和基本性质

堆是一种树形结构，有二叉树就有二叉堆。

• 二叉堆总是一棵完全二叉树
• 堆中某个结点的值总是不大于或不小于其父结点的值
• 根节点的值为整个堆中的最小/最大值。
  • 父节点中的值大于等于两个子节点中的值，根节点的值最大的堆称为大根堆。
  • 父节点中的值小于等于两个子节点中的值，根节点的值最小的堆称为小根堆。
• 我们可以在堆中插入和删除元素，然后通过调整元素的位置来维护堆的性质。

堆的操作

• 堆的初始化
  在建立堆之前，需要初始化一些东西：
  • 一个空数组，用于存储堆中的元素
  • 一个记录堆中元素个数的变量

    const int MAXSIZE = 10000;
    int len = 0;
    int heap[MAXSIZE + 1];

• 堆中元素的插入
  堆在插入时，需要首先将插入元素放在数组末尾，然后插入元素不断的和其父节点比较，直到位置合适。下面是对小根堆插入过程的模拟：
  
  小根堆插入的代码如下：

  void insert(int x) {
      heap[++len] = x;
      up(len);
  }
  
  void up(int k) {
      while(k > 1 && heap[k] < heap[k/2]) {
          swap(heap[k], heap[k/2]);
          k /= 2;
      }
  }
  
  int main(void) {
      insert(x);
      return 0;
  }

  大根堆和小根堆插入元素的方式基本相同，只需要改变大于/小于符号，插入操作的时间复杂度为 $O(log;n)$
• 堆顶元素的删除
  堆最常用的功能就是维护最小/最大值。在使用小根堆时，我们经常会求得最小的数字，然后让它出堆，这时就要从堆中删除堆顶数据。
  这时除了堆顶为空，它的左子树堆和右子树堆仍满堆结构。为了操作简单，一般选择将堆尾部元素放到堆顶，然后将其逐步下移的方式，下移时，如进行交换操作，交换的是该节点左右儿子中较小的一个与该节点。
  下图模拟小根堆删除堆顶元素的操作：
  
  小根堆删除元素的代码如下：

  void pop(void) {
      swap(heap[1], heap[len]);
      len--;
      down(1);
  }
  
  void down(void) {
      while(k * 2 <= len) {
          int j = k * 2;
          if(k*2+1 < len && heap[j+1] < heap[j])  j++;
          if(heap[k] <= heap[j])  break;
          swap(heap[k], heap[j]);
          k = j;
      }
  }

• 堆中任意位置的删除
  删除堆中的任意一个元素时，我们可以发现这个时候这个元素下的左子树堆和右子树堆也满足堆结构，但是我们不可以像删除堆顶节点一样，和数组尾部元素互换，然后尝试下移，原因如下：
  
  此时无需向下调整，因为 $5<8$ 且 $5<9$，依旧满足小根堆的性质，但是其父节点 $6>5$，破坏了小根堆的性质，因此此时需要上移。
  所以我们删除堆中的任意一个元素，跟数组尾元素互换时，不仅要考虑下移，还有可能会上移。小根堆中删除一个位于数组位置 pos 的元素的代码如下:

  void deleteElem(int pos) {
      if (pos == len) {
          heap[len] = 0;
          len--;
          return;
      }
      int x = heap[pos], y = heap[len];
      swap(heap[pos], heap[len]);
      len--;
      if (y < x) {
          // 堆尾的数比原数大, 尝试上移
          up(pos);
      } else {
          // 堆尾的数比原数小, 尝试下移
          down(pos);
      }
  }

STL 中的 priority_queue(优先队列)

STL 库中的 priority_queue 是一个很类似于堆的结构，它包含如下操作：

• empty - 判断是否为空
• size - 返回队列内元素个数
• top - 访问队首元素
• push - 往队列中插入一个元素
• pop - 弹出队首元素

这里的 priority_queue 相当于堆，队首元素相当于堆顶元素。
我们可以使用如下语句创建一个小根堆：

priority_queue<int, vector<int>, greater<int>> q;

这段C++语句创建了一个优先队列 q，其中元素类型为 int，底层容器使用 vector<int>，并且使用 greater<int> 作为比较器。在优先队列中，当元素被插入队列时，会根据比较器的规则进行排序，从而实现堆的性质。

在这段语句中，greater<int> 是一个函数对象，代表使用“大于”运算符进行比较。因此，当要创建一个小根堆时，即希望队列中的元素按照从小到大的顺序排列，可以利用 greater 作为比较器，这样队列中的最小元素将位于队首。
同样的，我们可以使用如下语句创建一个大根堆：

// 写法 1：
priority_queue<int> q;
// 写法 2：
priority_queue<int, vector<int>, less<int>> q;

当使用 priority_queue<int, vector<int>, greater<int>> q; 创建一个小根堆后，可以按以下方式操作这个小根堆：

• 插入元素：使用 push() 方法将元素插入小根堆。

  q.push(5); // 插入元素5
  q.push(3); // 插入元素3
  q.push(7); // 插入元素7

• 获取堆顶元素：使用 top() 方法获取小根堆的头部元素。

  int topElement = q.top(); // 获取小根堆的头部元素
  cout << "Top element of the min heap: " << topElement << endl;

• 删除堆顶元素：使用 pop() 方法删除小根堆顶部的元素。

  q.pop(); // 删除小根堆的头部元素

• 查看堆是否为空：使用 empty() 方法检查小根堆是否为空。

  if (q.empty()) {
      cout << "Min heap is empty" << endl;
  } else {
      cout << "Min heap is not empty" << endl;
  }