#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

int min(int a,int b)

{

return a>b?b:a;

}

template<class T> //堆的实现

class Heap

{

vector<T> vec;

int size;

public:

void BuildHeap();

void PercolateDown(int h);

void PercolatUp();

explicit Heap(int max=100):vec(max),size(0) {}

explicit Heap(const vector<T>& vt);

inline bool Empty()const

{

return size==0;

}

inline int Size(void)

{

return (size);

}

void Insert(const T&item);

inline const T& Top(void)const

{

return (vec[0]);

}

void DeleteMin(void);

void DeleteMin(T& item);

inline void Clear()

{

size=0;

}

};

template <class T>

void Heap<T>::DeleteMin() //删除根节点

{

if(size==0)

{

cout<<"Heap empty!";

exit(1);

}

vec[0]=vec[size-1];

size--;

PercolateDown(0);

}

template <class T>

void Heap<T>::DeleteMin(T& item) //删除根节点 并将删除的结点传给item

{

if(size==0)

{

cout<<"Heap empty!";

exit(1);

}

item=vec[0];

vec[0]=vec[size-1];

size--;

PercolateDown(0);

}

template <class T> //向上调整小根堆

void Heap<T>::PercolatUp()

{

int c=size-1,p=(c-1)/2;

T temp=vec[c];

while(c>0)

{

if(vec[p]<=temp)

{

break;

}

else

{

vec[c]=vec[p];

c=p;

p=(c-1)/2;

}

}

vec[c]=temp;

}

template <class T> //从第h个结点开始向下调整小根堆

void Heap<T>::PercolateDown(int h)

{

int p=h,c=2*p+1;

T temp=vec[p];

while(c<size)

{

if(c+1<size&&vec[c+1]<vec[c])

{

++c;

}

if(temp<=vec[c])

{

break;

}

else

{

vec[p]=vec[c];

p=c;

c=2*p+1;

}

}

vec[p]=temp;

}

template<class T>

void Heap<T>::Insert(const T&item) //插入一个结点并调整为堆

{

if(size==vec.size())

{

vec.resize(vec.size()*2);

}

vec[size]=item;

size++;

this->PercolateUp();

}

template<class T> //建堆

void Heap<T>::BuildHeap()

{

for(int i=size/2-1; i>=0; i--)

{

PercolateDown(i);

}

}

template <class T> //构造函数

Heap<T>::Heap(const vector<T>& vt):vec(vt.size()+10),size(vt.size())

{

for(int i=0; i<size; i++)

{

vec[i]=vt[i];

}

BuildHeap();

}

int main()

{

ios::sync_with_stdio(false);

vector<int> v;

int t,i;

cout<<"输入测试用例数目:"<<endl;

cin>>t;

while(t--)

{

//for(i=1;i<10;i++)

// v.push_back(rand()%100);

int n;

cout<<"输入堆的结点数:"<<endl;

cin>>n;

cout<<"输入"<<n<<"个结点的值:"<<endl;

for(i=0; i<n; i++)

{

int a;

cin>>a;

v.push_back(a);

}

Heap<int> h(v);

v.clear();

int x;

while(!h.Empty())

{

h.DeleteMin(x);

v.push_back(x);

}

cout<<"堆排序后:"<<endl;

for(i=0; i<(int)v.size(); i++)

{

cout<<v[i]<<' ';

}

cout<<endl;

v.clear();

}

return 0;

}

 

这是第二次作业的代码，利用C++来实现堆

测试的main函数功能是堆排序