最大堆是堆的兩種形式之一。
根結點（亦稱為堆頂）的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆，又稱最大堆（大頂堆）。
大根堆要求根節點的關鍵字既大於或等於左子樹的關鍵字值，又大於或等於右子樹的關鍵字值。
基本介紹
- 中文名：最大堆
- 外文名：max heap
- 性質：二叉堆的兩種形式之一
- 亦稱：堆頂
- 類型：類似地可定義k叉堆
概念,實現,
概念
注意： ①堆中任一子樹亦是堆。 ②以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。
實現
template<class T>class MaxHeap {public: MaxHeap(int MaxHeapSize = 10); ~MaxHeap() {delete [] heap;} int Size() const {return CurrentSize;} T Max() {if (CurrentSize == 0) throw OutOfBounds(); return heap[1];} MaxHeap<T>& Insert(const T& x); MaxHeap<T>& DeleteMax(T& x); void Initialize(T a[], int size, int ArraySize); void Deactivate() {heap = 0;} void Output() const;private: int CurrentSize, MaxSize; T *heap;};template<class T>MaxHeap<T>::MaxHeap(int MaxHeapSize){ MaxSize = MaxHeapSize; heap = new T[MaxSize+1]; CurrentSize = 0;}template<class T>MaxHeap<T>& MaxHeap<T>::Insert(const T& x){ if (CurrentSize == MaxSize) throw NoMem(); //為x尋找應插入的位置 //i從新的葉節點開始，並沿著樹上升 int i = ++CurrentSize; while (i != 1 && x > heap[i/2]) { heap[i] = heap[i/2]; // 將元素下移 i /= 2; // 移向父節點 } heap[i] = x; return *this;}template<class T>MaxHeap<T>& MaxHeap<T>::DeleteMax(T& x){ if (CurrentSize == 0) throw OutOfBounds(); x = heap[1]; T y = heap[CurrentSize--]; //最後一個元素 // 從根開始, 為y尋找合適的位置 int i = 1, // 堆的當前節點 ci = 2; // i的子節點 while (ci <= CurrentSize) { // 使heap[ci] 是i較大的子節點 if (ci < CurrentSize && heap[ci] < heap[ci+1]) ci++; // 能把y放入heap[i]嗎? if (y >= heap[ci]) break;//能 //不能 heap[i] = heap[ci]; // 子節點上移 i = ci; // 下移一層 ci *= 2; } heap[i] = y; return *this;}template<class T>void MaxHeap<T>::Initialize(T a[], int size, int ArraySize){ delete [] heap; heap = a; CurrentSize = size; MaxSize = ArraySize; // 產生一個最大堆 for (int i = CurrentSize/2; i >= 1; i--) { T y = heap[i]; // 子樹的根 // 尋找放置y的位置 int c = 2*i; // c 的父節點是y的目標位置 while (c <= CurrentSize) { // 使heap[c]是較大的子節點 if (c < CurrentSize && heap[c] < heap[c+1]) c++; // 能把y放入heap[c/2]嗎? if (y >= heap[c]) break; // 能 // 不能 heap[c/2] = heap[c]; // 子節點上移 c *= 2; // 下移一層 } heap[c/2] = y; }}template<class T>void MaxHeap<T>::Output() const{ cout << "The " << CurrentSize << " elements are"<< endl; for (int i = 1; i <= CurrentSize; i++) cout << heap[i] << ' '; cout << endl;}