最小堆，是一種經過排序的完全二叉樹，其中任一非終端節點的數據值均不大於其左子節點和右子節點的值。
基本介紹
- 中文名：最小堆
- 類型：完全二叉樹
- 屬於：二叉堆
- 屬性：概念定義
介紹,最小堆的實現,
介紹
堆是一種經過排序的完全二叉樹，其中任一非終端節點的數據值均不大於（或不小於）其左子節點和右子節點的值。
最大堆和最小堆是二叉堆的兩種形式。
最大堆：根結點的鍵值是所有堆結點鍵值中最大者。
最小堆：根結點的鍵值是所有堆結點鍵值中最小者。
而最大-最小堆集結了最大堆和最小堆的優點，這也是其名字的由來。
最大-最小堆是最大層和最小層交替出現的二叉樹，即最大層結點的兒子屬於最小層，最小層結點的兒子屬於最大層。
以最大（小）層結點為根結點的子樹保有最大（小）堆性質：根結點的鍵值為該子樹結點鍵值中最大（小）項。
最小堆的實現
#include <iostream>
using namespace std;
template<class T>
class MinHeap{
private:
T *heap; //元素數組，0號位置也儲存元素
int CurrentSize; //目前元素個數
int MaxSize; //可容納的最多元素個數
void FilterDown(const int start,const int end); //自上往下調整，使關鍵字小的節點在上
void FilterUp(int start); //自下往上調整
public:
MinHeap(int n=1000);
~MinHeap();
bool Insert(const T &x); //插入元素
T RemoveMin(); //刪除最小元素
T GetMin(); //取最小元素
bool IsEmpty() const;
bool IsFull() const;
void Clear();
};
template<class T>
MinHeap<T>::MinHeap(int n){
MaxSize=n;
heap=new T[MaxSize];
CurrentSize=0;
}
template<class T>
MinHeap<T>::~MinHeap(){
delete []heap;
}
template<class T>
void MinHeap<T>::FilterUp(int start){//自下往上調整
int j=start,i=(j-1)/2; //i指向j的雙親節點
T temp=heap[j];
while(j>0){
if(heap[i]<=temp)
break;
else{
heap[j]=heap[i];
j=i;
i=(i-1)/2;
}
}
heap[j]=temp;
}
template<class T>
void MinHeap<T>::FilterDown(const int start,const int end）{//自上往下調整，使關鍵字小的節點在
int i=start,j=2*i+1;
T temp=heap[i];
while(j<=end){
if( (j<end) && (heap[j]>heap[j+1]) )
j++;
if(temp<=heap[j])
break;
else{
heap[i]=heap[j];
i=j;
j=2*j+1;
}
}
heap[i]=temp;
}
template<class T>
bool MinHeap<T>::Insert(const T &x){
if(CurrentSize==MaxSize)
return false;
heap[CurrentSize]=x;
FilterUp(CurrentSize);
CurrentSize++;
return true;
}
template<class T>
T MinHeap<T>::RemoveMin( ){
T x=heap[0];
heap[0]=heap[CurrentSize-1];
CurrentSize--;
FilterDown(0,CurrentSize-1); //調整新的根節點
return x;
}
template<class T>
T MinHeap<T>::GetMin(){
return heap[0];
}
template<class T>
bool MinHeap<T>::IsEmpty() const{
return CurrentSize==0;
}
template<class T>
bool MinHeap<T>::IsFull() const{
return CurrentSize==MaxSize;
}
template<class T>
void MinHeap<T>::Clear(){
CurrentSize=0;
}
//最小堆：根結點的鍵值是所有堆結點鍵值中最小者。
int main (){
int k,n=11,a[11]={0,5,2,4,9,7,3,1,10,8,6};
MinHeap<int> test(11);
for(k=0; k<n; k++)
test.Insert(a[k]);
cout<<test.IsFull()<<endl;
for(k=0;k<n;k++)
cout<<test.RemoveMin()<<ends;
cout<<endl;
return 0;
}
如果有一個關鍵字的集合K={k0,k1,k2, ..., kn-1}, 把所有元素按完全二叉樹的順序存儲方式存放在一個一維數組中，並且滿足ki <= k2i+1 且 ki <= k2i+2 (i = 0, 1, ..., (n-2)/2 向上取整)則稱這個集合為小根堆。
