一個大小為n的堆是一棵包含n個結點的完全二叉樹, 該樹中每個結點的關鍵字值大于等于其雙親結點的關鍵字值.? 堆頂: 二叉樹的根, 它的關鍵字是整棵樹上最小的.(最小堆) 建堆運算時, CreatHeap()函數完成將一個以任意次序排列的元素排列, 通過向下調整建成最小堆. 實現運算AdjustDown的方法是: 向下調整heap[r]. 設tmp = hear[r], 如果tmp大于其左, 右孩子中的較小者, 則將tmp與該較小元素交換,? 調整后繼續將tmp與它的左右孩子比較. 如果比較小的孩子大, 則繼續交換. 直到不需要再調整或者已經到堆底. 實現代碼: ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" using namespace std; template <class T> void AdjustDown(T heap[], int r, int j) { int child = 2 * r + 1; T tmp = heap[r]; while(child <= j) { if(child < j && heap[child] > heap[child + 1]) child++; if(tmp < heap[child]) break; heap[(child - 1) / 2] = heap[child]; child = 2 * child + 1; } heap[(child - 1) / 2] = tmp; for(int i = 0; i <= j; ++i) cout << heap[i] << "\t"; cout << endl; } template <class T> void CreatHeap(T heap[], int n) { for(int i = (n - 2) / 2; i > -1; --i) AdjustDown(heap, i, n - 1); } int main(int argc, char const *argv[]) { int heap[] = {61, 28, 81, 43, 36, 47, 83, 5}; for(int i = 0; i < 8; ++i) cout << heap[i] << "\t"; cout << endl; CreatHeap(heap, 8); return 0; } ~~~