1 template<class ElementType>
 2 class MinHeap
 3 {
 4 public:
 5     MinHeap(ElementType array[], int maxHeapSize);
 6     ~MinHeap() { delete [] heap; }
 7     int insertHeap(const ElementType &item);                    // 向堆中插入一个元素
 8     int removeHeap(ElementType &item);                          // 堆是否为空
 9     bool isEmpty();         
10 private:            
11     ElementType *heap;                                          // 存储堆的数组
12     int currentLength;                                          // 堆的当前长度
13     int maxHeapSize;                                            // 堆的最大存储空间
14     void siftDown(int nodeIndex);                               // 从结点号nodeIndex开始自顶向下调整堆
15     void siftUp(int nodeIndex);                                 // 从结点号nodeIndex开始自底向上调整堆
16 };

1 /*
2  * 定义堆的顺序存储类型
3  */
4 struct HeapSequence
5 {
6     ElementType *heap;          // 定义指向存放堆的数组指针
7     int currentLength;          // 定义堆的长度
8     int MAXSIZE;                // 堆数组的最大空间
9 };

  1 /*
  2  * 初始化堆
  3  */
  4 void initHeap(HeapSequence &HBT, int maxSize)
  5 {
  6     if(maxSize <= 0) {
  7         cout << "The real parameter 'maxSize' is invalid!\n";
  8         exit(-1);
  9     }
 10     HBT.heap = new ElementType[maxSize];
 11     if(HBT.heap == NULL) {
 12         cout << "Allocate memory failed!\n";
 13         exit(-1);
 14     }
 15     HBT.MAXSIZE = maxSize;
 16     HBT.currentLength = 0;                                          // 置堆为空
 17 }
 18 
 19 /*
 20  * 检查堆是否为空
 21  */
 22 bool isEmpty(HeapSequence &HBT)
 23 {
 24     return HBT.currentLength == 0;
 25 }
 26 
 27 /*
 28  * 清除堆
 29  */
 30 void clearHeap(HeapSequence &HBT)
 31 {
 32     delete HBT.heap;
 33     HBT.heap = NULL;
 34     HBT.currentLength = 0;
 35 }
 36 
 37 /*
 38  * 向堆中插入一个元素
 39  */
 40 void insertHeap(HeapSequence &HBT, ElementType item)
 41 {
 42     /* 处理堆空间满的情况 */
 43     if(HBT.currentLength == HBT.MAXSIZE) {    
 44         ElementType *newArray = new ElementType[HBT.MAXSIZE * 2]);      // 存储空间扩大一倍
 45         if(newArray == NULL) {
 46             cout << "Allocate memory failed!\n";
 47             exit(-1);
 48         }
 49         for(int index = 0; index < HBT.MAXSIZE; ++index)                // 将堆中原有数据放入新的存储空间
 50             newArray[index] = HBT.heap[index];
 51         delete HBT.heap;                                                // 释放原有空间
 52         HBT.heap = newArray;                                            // 堆指针指向新的空间
 53         HBT.MAXSIZE = HBT.MAXSIZE * 2;                                  // 修改堆空间大小
 54     }
 55 
 56     /* 新元素加入堆尾 */
 57     HBT.heap[HBT.currentLength] = item;
 58     ++HBT.currentLength;
 59 
 60     /* 自下而上的调整堆 */
 61     ElementType temp = item;                                            // 暂存新元素
 62     int down = HBT.currentLength - 1;                                   // down指示待调整位置
 63     while(down > 0) {                                                   // 从插入位置开始逐层向上调整
 64         int up = (down - 1) / 2;                                        // 找到待调整的元素的父亲节点
 65         if(temp >= HBT.heap[up])                                        // 若该层已经是小顶堆，则结束调整过程
 66             break;              
 67         HBT.heap[down] = HBT.heap[up];                                  // 对上一层调整
 68         down = up;              
 69     }               
 70     HBT.heap[down] = temp;                                              // 把插入元素放入最终位置
 71 }
 72 
 73 /*
 74  * 删除堆顶元素
 75  */
 76 ElementType removeHeap(HeapSequence &HBT)
 77 {
 78     /* 堆空 */
 79     if(HBT.currentLength == 0) {
 80         cout << "The heap is empty!\n";
 81         exit(-1);
 82     }
 83 
 84     /* 自顶向下调整堆 */
 85     ElementType temp = HBT.heap[0];
 86     --HBT.currentLength;
 87     // 1、堆只有一个元素
 88     if(HBT.currentLenght == 0)     
 89         return temp;
 90     // 2、堆有多个元素
 91     ElementType tailValue = HBT.heap[HBT.currentLength];
 92     int up = 0;                                                                  // up指向待调整元素，开始指向根结点
 93     int down = 2 * up + 1;                                                              // down指向up结点的左孩子
 94     // 逐层向下调整，直到待调整结点为叶子结点(“筛选”)
 95     while(down <= HBT.currentLength - 1) {
 96         if((down < HBT.currentLength - 1) && (HBT.heap[down] > HBT.heap[down + 1]))     // 使down指向左右孩子中值小者
 97             ++down;
 98         if(tailValue <= HBT.heap[down])                                          // 若到某层已经是小顶堆，则终止调整过程
 99             break;
100         HBT.heap[up] = HBT.heap[down];                                                  // 孩子结点值移交值父亲结点
101 
102         // 对下一层开始调整
103         up = down;
104         down = 2 * up + 1;
105     }
106     HBT.heap[up] = tailValue;                                                           // 待调整元素放入最终位置
107 
108     return temp;                                                                        // 返回堆顶删除的元素
109 }