//用習慣了STL_heap自己來寫一個,類實現。
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 100
class my_heap
{
public:
int array[N];
int cnt;
my_heap()
{
for(int i=0;i<N;i++)
array[i]=0;
cnt=0;
}
void push(int num);
int pop();
};
void my_heap::push(int num)
{
array[++cnt]=num;
int i=cnt,j=i/2;
while(j>0)
{
if(array[i]>array[j])
swap(array[i],array[j]);
else break;
i=j;j=i/2;
}
}
int my_heap::pop()
{
int num=array[1],maxc;
swap(array[1],array[cnt]);
cnt--;
int i=1,j=2*i;
while(j<=cnt)
{
if(j+1>cnt) maxc=j;
else maxc=array[j]>array[j+1]?j:j+1;
if(array[maxc]>array[i])
swap(array[i],array[maxc]);
else break;
i=maxc;j=2*i;
}
return num;
}
int main()
{
int num;
my_heap h;
while(scanf("%d",&num),num)
h.push(num);
while(h.cnt)
printf("%d ",h.pop());
printf("\n");
for(int i=1;h.array[i]&&i<N;i++)
printf("%d ",h.array[i]);
printf("\n");
return 0;
}
測試數據及結果：
1 4 9 88 56 21 45 7 6 3 99 1452 122 34 2 0
1452 122 99 88 56 45 34 21 9 7 6 4 3 2 1
1 2 3 4 6 7 9 21 34 45 56 88 99 122 1452
Press any key to continue