#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
template<class T>
class MinHeap
{
private:
T *heap;
int CurrentSize;
int MaxSize;
void FilterDown(const int start,const int end);
void FilterUp(int start);
public:
MinHeap(int n);
MinHeap();
~MinHeap(){delete []heap;}
bool Insert(const T &x);
T RemoveMin();
T GetMin();
bool IsEmpty() const{return CurrentSize==0;}
bool IsFull() const{return CurrentSize==MaxSize;}
void Clear(){CurrentSize=0;}
};
template<class T>
MinHeap<T>::MinHeap()
{
MaxSize=1000;
heap=new T[MaxSize];
CurrentSize=0;
}
template<class T>
MinHeap<T>::MinHeap(int n)
{
MaxSize=n;
heap=new T[MaxSize];
CurrentSize=0;
}
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>
void MinHeap<T>::FilterUp(int start)
{
int j=start,i=(j-1)/2;
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>
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];
}
int main ()
{
MinHeap<int> test(8);
int k;
bool tem;
for(k=1;k<=10;k++)
{
tem=test.Insert(10-k);
}
tem=test.IsEmpty();
tem=test.IsFull();
for(k=1;k<=5;k++)
test.RemoveMin();
return 0;
}一個自實現(xiàn)的優(yōu)先隊列 最小堆。
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
template<class T>
class MinHeap
{
public:
T *heap;
int CurrentSize;
int MaxSize;
void FilterDown(const int start,const int end);
void FilterUp(int start);
public:
MinHeap(int n);
~MinHeap(){delete []heap;}
bool Insert(const T &x);
T RemoveMin();
T GetMin();
};
template<class T>
MinHeap<T>::MinHeap(int n)
{
MaxSize=n;
heap=new T[MaxSize];
CurrentSize=0;
}
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+1]<heap[j])
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>
void MinHeap<T>::FilterUp(int start)
{
int j=start,i=(j-1)/2;
T temp=heap[j];
while(j>0)
{
if(heap[i]<temp) break;
else heap[j]=heap[i];j=i;i=(i-1)>>1;
}
heap[j]=temp;
}
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];
}
稍微改良一下啊 只需要重載<符號即可