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 HeapSequence5 {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 =http://www.mamicode.com/ 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 }