/* MinHeap.cpp */
template <class E>
MinHeap<E>::MinHeap(int sz){
    maxHeapSize = (DefaultSize < sz)?sz:DefaultSize;
    heap = new E[maxHeapSize];
    if(heap == NULL){cerr<<"堆存储分配失败!"<<endl;exit(1);}
       currentSize=0;
};
      
template <class E>//数组指针作为形参一般需要传递数组大小n,防止数组越界
MinHeap<E>::MinHeap(E arr[], int n){
       maxHeapSize = (DefaultSize < n)?n:DefaultSize; //扩大数组上限为n
       heap = new E[maxHeapSize];
       if(heap == NULL){cerr<<"堆存储分配失败!"<< endl;exit(1);}
       for(int i=0;i<n;i++) heap[i]=arr[i];
       currentSize = n;
       int currentPos =(currentSize-2)/2;
       while(currentPos>=0){
       siftDown(currentPos,currentSize-1);
       currentPos--;
       }
};
template <class E>
void MinHeap<E>::siftDown(int start, int m){
       int i = start,j = 2*i+1;
       E temp = heap[i];
       while(j <= m){
              if( j<m&&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 E>
void MinHeap<E>::siftUp(int start){
       int j = start, i =(j-1)/2; E 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 E>
bool MinHeap<E>::Insert(const E& x){
       if(currentSize == maxHeapSize)
              {cerr<<"Heap Full"<<endl; return false;}
       heap[currentSize]=x;
       siftUp(currentSize);
       currentSize++;
       return true;
};
template <class E>
bool MinHeap<E>::RemoveMin(E& x){
       if(!currentSize){cout<<"Heap empty"<<endl;return false;}
       x=heap[0];heap[0]=heap[currentSize-1];
       currentSize--;
       siftDown(0,currentSize-1);
       return true;
};


这两个都是从书上摘抄的，最小堆没什么问题，最大堆是修改过的，目前没测试出什么问题。
不过没有封装进去排序，但是用这个类排序很简单。也可以每次都把堆顶的数据取出放入一个
数组。也就相当于排序了。

void prtElements(int brN,int a) //按格式输出数组元素
{
int i;
for(i=0;i<brN;i++) printf(" ");
printf("%d",a);
for(i=0;i<brN+1;i++) printf(" ");
}
void prtBarV(int brN) //垂直连接线输出
{
int i;
for(i=0;i<brN;i++) printf(" ");
printf("|");
for(i=0;i<brN+1;i++) printf(" ");
}
void prtBar(int brN) //水平连接线输出
{
int i;
for(i=0;i<(brN-1)/2;i++) printf(" ");
for(i=(brN-1)/2;i<brN;i++) printf("-");
printf("+");
for(i=0;i<brN/2+1;i++) printf("-");
for(i=brN/2+1;i<brN+1;i++) printf(" ");
}


void prtHeap()
{
int i,k,j=0,v=1,vFinal; //v存储每行的输出个数
for(i=0;i<=N-1;i++)//计算最后一行的输出个数作为模板
{
//printf("%d ",a[i]);
if((i+1)==f2(j))
{
       //printf("\n");
       j++;
       v*=2;
}
}
//printf("\n\n");
vFinal = v; //存储模板中最后一行的输出个数
v=1,j=0;
for(i=0;i<=N-1;i++)//按模板构造堆视图
{
prtElements((vFinal/v)-1,a[i]);
if((i+1)==f2(j))
{
printf("\n");
for(k=0;k<v;k++)
   prtBarV((vFinal/v)-1);
printf("\n");
for(k=0;k<v;k++)
   prtBar((vFinal/v)-1);
printf("\n");
       j++;
       v*=2;
}
}
}


int main(int argc, char* argv[])
{
int i;
MinHeap<int> minhp(a,N);
MaxHeap<int> maxhp(a,N);
start = clock();
for (i = 0; i < MAX; ++i)
{
printf("调整前：\n");
prtHeap();//调用被测试的函数
for(int j=0;j<N; j++)
a[j]=minhp.GetHeap(j);
printf("\n\n最小堆：\n");
prtHeap();
for(j=0;j<N; j++)
a[j]=maxhp.GetHeap(j);
printf("\n\n最大堆：\n");
prtHeap();
}
end = clock();
printf("\n\n平均用时%10.8lf秒\n\n", (double)(end - start) / CLOCKS_PER_SEC / MAX);
getch();
return 0;
}


附上调试堆得效果图，大家可以试一试。很有趣。

上边就是CMD下的堆视图。算是数组存储。此外还有一种链表存储，在操作系统和编译器里边使用得很多。
比如，new 和 malloc 函数就是使用链表堆在内存中寻找空间。我是这样理解的，如有错误希望大家指出。

回复：45楼
原来万元是小萌啊= -

蒽

挖坟