最小堆

最小堆,是一種經過排序的完全二叉樹,其中任一非終端節點的數據值均不大於其左子節點和右子節點的值。

介紹

堆是一種經過排序的完全二叉樹,其中任一非終端節點的數據值均不大於(或不小於)其左子節點和右子節點的值。

最大堆和最小堆是二叉堆的兩種形式。

最大堆:根結點的鍵值是所有堆結點鍵值中最大者。

最小堆:根結點的鍵值是所有堆結點鍵值中最小者。

而最大-最小堆集結了最大堆和最小堆的優點,這也是其名字的由來。

最大-最小堆是最大層和最小層交替出現的二叉樹,即最大層結點的兒子屬於最小層,最小層結點的兒子屬於最大層。

以最大(小)層結點為根結點的子樹保有最大(小)堆性質:根結點的鍵值為該子樹結點鍵值中最大(小)項。

最小堆的實現

#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 向上取整)則稱這個集合為小根堆。

相關詞條

相關搜尋

熱門詞條

聯絡我們