关于堆的描述可以参考：
我的实现没有用二叉树，而是用数组。上文提到，由于堆是一种complete树（complete，和完全树略有区别），即子节点的上层是完全树，而子节点从左向右严格排列，这种数据结构可以用数组很好模拟。从第一层第一个节点为1开始，从左到右从上到下依次存储。则，对于某个索引为i的节点，其左子节点和右子节点的索引分别为：
i * 2， i * 2 + 1
C++代码：
#includeusing namespace std;template class doubleHeap{public: doubleHeap( int _size, int _type // 1 : max heap 2 : min heap ); void extractTop(T &top); void deleteTop(); bool addElement(T _new_element); bool empty(); bool full(); void printHeap(int root, int level); // for debugprivate: void swap(int i, int j); int leftChild(int i); int rightChild(int i); int parent(int i); bool comp(int i, int j); // if the nodes should exchangeprivate: T *data; int max_size; int size; int type;};template doubleHeap ::doubleHeap(int _size, int _type){ max_size = 10; if(_size >= 10) max_size = _size; data = new T[max_size]; size = 0; type = 1; // default max heap if(_type == 1 || type == 2) type = _type;}template void doubleHeap ::extractTop(T &top){ if(size == 0) return; top = data[0];}template void doubleHeap ::deleteTop(){ if(size == 0) return; data[0] = data[size - 1]; size --; int cur = 0; // start from the root int lChildIndex; int rChildIndex; // begin exchanging the node and check if it's been a heap while(true) { if(cur >= size) // the heap is null break; rChildIndex = rightChild(cur); lChildIndex = leftChild(cur); if(lChildIndex >= size) // right child and left child has been a null break; else if(rChildIndex >= size) // rightChild null, left not { if(comp(cur, lChildIndex)) { swap(cur, lChildIndex); cur = lChildIndex; } else break; // has been a heap } else // left and right are not null { if(comp(cur, rChildIndex) || comp(cur, lChildIndex)) { if(comp(lChildIndex, rChildIndex)) { swap(cur, rChildIndex); cur = rChildIndex; } else { swap(cur, lChildIndex); cur = lChildIndex; } } else break; } }}template bool doubleHeap ::addElement(T _new_element){ data[size] = _new_element; size ++; int cur = size - 1; int parentIndex; while(true) { if(cur == 0) break; parentIndex = parent(cur); if(comp(parentIndex, cur)) { swap(cur, parentIndex); cur = parentIndex; } else break; }}template bool doubleHeap ::empty(){ return size == 0;}template bool doubleHeap ::full(){ return max_size == size;}template void doubleHeap ::swap(int i, int j){ T ex; ex = data[i]; data[i] = data[j]; data[j] = ex;}template int doubleHeap ::leftChild(int i){ return 2 * (i + 1) - 1;}template int doubleHeap ::rightChild(int i){ return 2 * (i + 1);}template int doubleHeap ::parent(int i){ return (i + i) / 2 - 1;}template bool doubleHeap ::comp(int i, int j){ if(type == 1) // max heap { return data[i] < data[j]; } else // min heap { return data[i] > data[j]; }}template void doubleHeap ::printHeap(int root, int level){ int i; if(root >= size) return; printHeap(leftChild(root), level + 1); for(i = 0; i < level; i ++) cout << "\t"; cout << data[root] << endl; printHeap(rightChild(root), level + 1);}int main(){ int a[] = { 1, 10, 6, 23, 7, 8, 90, 12, 45, 76, 33, 25, 3, 17, 70, 10}; int i, aLen = 16, e; doubleHeap maxHeap(100, 1); for(i = 0; i < aLen; i ++) { maxHeap.addElement(a[i]); } maxHeap.printHeap(0, 0); // heap sort while(!maxHeap.empty()) { maxHeap.extractTop(e); cout << e << " "; maxHeap.deleteTop(); } return 0;}
输出：
1 17 45 12 76 10 33 1090 8 25 7 70 6 23 390 76 70 45 33 25 23 17 12 10 10 8 7 6 3 1