binary-heap（二叉堆）原理及C++代码实现

二叉堆可以看做一个近似的完全二叉树，所以一般用数组来组织。

二叉堆可以分为两种形式：最大堆和最小堆。最大堆顾名思义，它的每个结点的值不能超过其父结点的值，因此堆中最大元素存放在根结点中。最小堆的组织方式刚好与最大堆相反，它的最小元素存放在根结点中。

维护堆性质最重要的两个算法就是向上维护和向下维护。简而言之，例如最大堆中根结点的值小于其子结点的值，这个时候就要向下维护，把根结点逐级下降到适合的位置。显而易见地，向上维护就是子结点的值比其父结点大时（最大堆中），将结点逐级上升到合适的位置。这两个方法保证堆的性质不会被破坏。

堆经常用来实现优先队列，最大堆就对应最大优先队列，最小堆同上。因为通过关键字来查找堆中具体元素的位置比较麻烦，所以一般通过在堆中存储对象的句柄，在对应的对象中也存储对应堆元素的句柄来直接定位到元素的位置。

二叉堆是堆中最容易实现的一种，也算是用的比较广泛的一种。我下面的代码给出了最大堆和最小堆的一部分关键操作，另外一部分则挑选其中一种来实现。

代码如下：（仅供参考）

1 class Node {
  2 public :
  3     int value;
  4 public :
  5     Node(int v = 0) : value(v) {}
  6 };
  7 
  8 class Heap {
  9     vector<Node> heap;
 10     int heap_size;
 11 
 12     int Left(int i) {return (i << 1) + 1;}  //下标从0开始
 13     int Right(int i) {return Left(i) + 1;}
 14     int Parent(int i) {return (i - 1) >> 1;}
 15     void MaxHeapify(int i);  //使结点i维持最大堆性质(向下维护)
 16     void MinHeapify(int i);  //使结点i维持最小堆性质(向下维护)
 17     void IncreaseKey(int i, int k);  //将结点i的value上升到k(向上维护)
 18 public :
 19     Heap() : heap_size(0) {}
 20     Heap(vector<Node> &t) : heap(t), heap_size(t.size()) {}
 21     void BuildMaxHeap();     //建立最大堆，时间复杂度O(n);
 22     void BuildMinHeap();     //建立最小堆，时间复杂度O(n);
 23     void MinHeapSort();     //从小到大排序，时间复杂度O(nlgn);
 24     void MaxHeapSort();     //从大到小排序，时间复杂度O(nlgn);
 25     //以下函数仅在最大堆下进行
 26     void Insert(int k); //插入一个元素（最大堆）
 27     void Delete(int i);    //删除一个元素（最大堆）
 28     Node Maximum();         //返回value最大的元素
 29     Node ExtractMax();     //去掉并返回value最大的元素
 30     //union two heap:union the vector of the two heaps, and call BuildMaxHeap()
 31     int Size() {return heap.size();} //返回vector的元素个数
 32     void PrintAll() {
 33         for (auto i : heap)
 34             cout << i.value << ends;
 35         cout << endl;
 36     }
 37 };
 38 
 39 void Heap::MaxHeapify(const int i) {
 40     int largest;
 41     if (Left(i) < heap_size && heap[Left(i)].value > heap[i].value)
 42         largest = Left(i);
 43     else
 44         largest = i;
 45     if (Right(i) < heap_size && heap[Right(i)].value > heap[largest].value)
 46         largest = Right(i);
 47     if (largest != i) {
 48         swap(heap[i], heap[largest]);
 49         MaxHeapify(largest);
 50     }
 51 }
 52 
 53 void Heap::MinHeapify(const int i) {
 54     int least;
 55     if (Left(i) < heap_size && heap[Left(i)].value < heap[i].value)
 56         least = Left(i);
 57     else
 58         least = i;
 59     if (Right(i) < heap_size && heap[Right(i)].value < heap[least].value)
 60         least = Right(i);
 61     if (least != i) {
 62         swap(heap[i], heap[least]);
 63         MinHeapify(least);
 64     }
 65 }
 66 
 67 void Heap::BuildMaxHeap() {
 68     heap_size = heap.size();
 69     for (int i = Parent(heap_size - 1); i >= 0; --i)
 70         MaxHeapify(i);
 71 }
 72 
 73 void Heap::BuildMinHeap() {
 74     heap_size = heap.size();
 75     for (int i = Parent(heap_size - 1); i >= 0; --i)
 76         MinHeapify(i);
 77 }
 78 
 79 void Heap::MinHeapSort() {
 80     BuildMaxHeap();
 81     for (int i = heap.size() - 1; i > 0; --i) {
 82         swap(heap[i], heap[0]);
 83         --heap_size;
 84         MaxHeapify(0);
 85     }
 86 }
 87 
 88 void Heap::MaxHeapSort() {
 89     BuildMinHeap();
 90     for (int i = heap.size() - 1; i > 0; --i) {
 91         swap(heap[i], heap[0]);
 92         --heap_size;
 93         MinHeapify(0);
 94     }
 95 }
 96 
 97 void Heap::Insert(int k) {
 98     heap.push_back(INT_MIN);
 99     IncreaseKey(heap.size() - 1, k);
100 }
101 
102 void Heap::Delete(int i) {
103     if (heap[heap.size() - 1].value > heap[i].value) {
104         IncreaseKey(i, heap[heap.size() - 1].value);
105         heap.pop_back();
106     } else {
107         heap[i] = heap[heap.size() - 1];
108         heap.pop_back();
109         heap_size = heap.size();
110         MaxHeapify(i);
111     }
112 }
113 
114 Node Heap::Maximum() {
115     return heap[0];
116 }
117 
118 Node Heap::ExtractMax() {
119     Node max = heap[0];
120     heap[0] = heap[heap.size() - 1];
121     heap.pop_back();
122     MaxHeapify(0);
123     return max;
124 }
125 
126 void Heap::IncreaseKey(int i, int k) {
127     if (k <= heap[i].value)
128         return ;
129     while (i > 0 && heap[Parent(i)].value < k) {
130         heap[i] = heap[Parent(i)];
131         i = Parent(i);
132     }
133     heap[i].value = k;
134 }

原文链接: https://www.cnblogs.com/yxsrt/p/12249557.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍