堆是一种完全二叉树。

  • 最大堆：对树中的每个结点来说，其结点的值都大于等于其孩子结点的值。
  • 最小堆：对树中的每个结点来说，其结点的值都小于等于其孩子结点的值。
  • 特性：最大堆中的最大值在堆顶，最小堆中的最小值在堆顶。

堆中操作：

  • 搜索堆顶元素。O(1)
  • 添加新结点。先将新结点添加到最后的位置，然后将该新结点的值与其父节点的值相比较，在最大堆中如果新结点值比父结点值大（也即父节点值比新结点值小，不符合最大堆的定义了，需要调整），则交换父子结点的数据；按照此方式逐层向上调整，直到到达堆顶或者父节点值大于等于新节点值。O(log(n))
  • 删除堆顶元素。在以vector为底层容器实现的最大堆中，堆顶元素并不直接删除，而是先将其（索引为0）与最后一个元素（索引为n-1）交换，然后堆的大小减一，vector中有效元素少一个，相当于删除了堆顶元素；然后将堆顶元素的值与其左右子结点元素的值相比，如果其左（右）孩子结点值在三者中最大，则交换根和左（右）孩子结点，然后递归调整左（右）孩子结点，直到到达叶子结点或者根节点值比左右孩子结点值都大。O(log(n))

最大堆（最小堆）常用优先队列（默认底层容器类是vector）实现。

最小堆实现

  1. #include <iostream>
  2. #include <vector>
  4. using namespace std;
  6. /**
  7.  * 以vector为底层容器的最小堆（完全二叉树）
  8.  * 有效元素从索引为0的位置开始存储，
  9.  * 索引为i的元素的左、右结点索引分别是2*i+1, 2*i+2，
  10.  * 索引为i的元素的父节点的索引是(i-1)/2，
  11.  * 最后一个非叶子节点索引为n/2-1。
  12.  */
  13. template <class DT>
  14. class MinHeap{
  15. private:
  16.     vector<DT> data;       // 存储元素使用的线性表
  17.     int n;                 // data中有效元素个数
  20.     void heapAdjust(int k){
  21.         // 将data中索引位置在[0,k]的元素调整为最小堆
  22.         // 有效元素k+1个，第一个非叶子节点的位置是（k+1）/2-1
  23.         int node_idx = (k+1)/2-1;
  24.         while(node_idx >= 0){
  25.             adjustNode(node_idx);
  26.             //this->print();
  27.             node_idx --;
  28.         }
  29.     }
  31.     void adjustNode(int i){
  32.         // 调整索引i位置的结点，它一定有左孩子，不一定有右孩子
  33.         int lc_idx = 2 * i + 1;         // 索引i的左子结点索引
  34.         int rc_idx = lc_idx + 1;        // 索引i的右子结点索引
  36.         if(lc_idx >= n){
  37.             // 左孩子不存在，那右孩子一定不存在，无需调整了。
  38.             return;
  39.         }
  40.         else if(rc_idx >= n){
  41.             // 左孩子存在，右孩子不存在
  42.             if(data[i] < data[lc_idx]){
  43.                 // 根节点值小于左子结点，无需调整
  44.                 return;
  45.             }
  46.             else{
  47.                 // 根节点值大于左子结点，交换根和左子结点
  48.                 this->swap(i, lc_idx);
  49.                 // 由于右孩子结点不存在，因此左孩子结点一定是叶子结点，无需递归调整左子节点
  50.             }
  51.         }
  52.         else{
  53.             // 左、右孩子都存在
  54.             if(data[i] < data[lc_idx] && data[i] < data[rc_idx]){
  55.                 // 根结点是最小的，无需调整
  56.                 return;
  57.             }
  58.             else if(data[lc_idx] < data[i] && data[lc_idx] < data[rc_idx]){
  59.                 // 左子结点最小的，根与左子结点交换，然后递归调整左子结点
  60.                 this->swap(i, lc_idx);
  61.                 adjustNode(lc_idx);
  62.             }
  63.             else{
  64.                 // 右子结点是最小的，根与右子结点交换，然后递归调整右子结点
  65.                 this->swap(i, rc_idx);
  66.                 adjustNode(rc_idx);
  67.             }
  68.         }
  69.     }
  71.     void swap(int i, int j){
  72.         // 交换索引位置在i,j处的元素
  73.         DT tmp = this->data[i];
  74.         this->data[i] = this->data[j];
  75.         this->data[j] = tmp;
  76.     }
  78.     void heapUp(int i){
  79.         // 新插入时调用，将索引为i的元素的值调整到正确的位置上
  80.         // 要求原来数据已经是最小堆
  81.         int root_idx = (i-1)/2;
  82.         if(root_idx < 0 || data[root_idx] < data[i]){
  83.             return;
  84.         }
  85.         else{
  86.             // 新结点值比根结点小
  87.             this->swap(root_idx, i);
  88.             this->heapUp(root_idx);
  89.         }
  90.     }
  92.     void heapDown(int i){
  93.         // 删除结点后调用
  94.         int lc_idx = 2 * i + 1;           // i的左孩子索引
  95.         int rc_idx = lc_idx + 1;          // i的右孩子索引
  96.         if(lc_idx >= this->n){
  97.             // 左孩子不存在，则右孩子肯定也不存在，无需调整
  98.             return;
  99.         }
  100.         else if(rc_idx >= this->n){
  101.             // 左孩子存在，右孩子不存在
  102.             if(data[i] < data[lc_idx]){
  103.                 // 根节点值小于左孩子结点值，已经是最小堆，无需调整
  104.                 return;
  105.             }
  106.             else{
  107.                 // 根节点值大于左孩子结点值，需要交换根和左孩子
  108.                 this->swap(i, lc_idx);
  109.                 // 因为左孩子已经是叶子结点，没有子树了，不用递归调整
  110.             }
  111.         }
  112.         else{
  113.             // 左右子结点都存在
  114.             if(data[i] < data[lc_idx] && data[i] < data[rc_idx]){
  115.                 // 根结点是三个中最小的，符合最小堆，无需调整了
  116.                 return;
  117.             }
  118.             else if(data[lc_idx] < data[i] && data[lc_idx] < data[rc_idx]){
  119.                 // 左孩子是三者中最小的，交换根和左孩子结点
  120.                 this->swap(i, lc_idx);
  121.                 // 递归向下调整左孩子结点
  122.                 this->heapDown(lc_idx);
  123.             }
  124.             else{
  125.                 // 右孩子是三者中最小的，交换根和右孩子结点
  126.                 this->swap(i, rc_idx);
  127.                 // 递归向下调整右孩子结点
  128.                 this->heapDown(rc_idx);
  129.             }
  130.         }
  131.     }
  133. public:
  134.     MinHeap():n(0){}
  135.     MinHeap(vector<DT> _data): data(_data), n(data.size()){
  136.         this->heapAdjust(n-1);
  137.     }
  139.     void push(DT x){
  140.         if(this->data.size() < n){
  141.             // data中有空余位置
  142.             this->data[n] = x;
  143.         }
  144.         else{
  145.             // data中每个位置都有元素，也即所有元素都是有效元素
  146.             this->data.push_back(x);
  147.         }
  149.         n += 1;
  150.         this->heapUp(n-1);
  151.         this->print();
  152.     }
  154.     void pop(){
  155.         if(this->empty()){
  156.             return;
  157.         }
  159.         this->swap(0, n-1);
  160.         n -= 1;
  161.         this->heapDown(0);
  162.         this->print();
  163.     }
  165.     DT& top(){
  166.         return data[0];
  167.     }
  169.     bool empty(){
  170.         return this->n <= 0;
  171.     }
  173.     void print() {
  174.         cout << "[";
  175.         if (n > 0) {
  176.             cout << this->data[0];
  177.         }
  178.         for (int i = 1; i < n; i++) {
  179.             cout << "," << this->data[i];
  180.         }
  181.         cout << "]" << endl;
  182.     }
  183. };
  185. int main() {
  186.     MinHeap<int> mh(vector<int>({7, 4, 3, 5, 9, 8, 1, 2}));
  187.     vector<int> nv({91, 14, 23, 41, 22, 11, 87, 90});
  188.     for(int v : nv){
  189.         mh.push(v);
  190.     }
  192.     while (!mh.empty()){
  193.         cout << mh.top() << " , ";
  194.         mh.pop();
  195.     }
  196.     cout << endl;
  198.     return 0;
  199. }