本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/%e5%a0%86%e7%9a%84%e7%ae%80%e5%8d%95%e5%ae%9e%e7%8e%b0%e5%92%8c%e5%ba%94%e7%94%a8/
一、用数组存储的堆和由此堆上实现的简单排序。 虽然对排序保证了最坏情况下的O(n log n)的性能，但对于常见输入，最快的堆排序也比简单快速排序慢。
#include<iostream>
using namespace std;
int x[100];
void siftup(int n)
{
int p;
int i = n;
while(1){
if(i == 1)
break;
p = i / 2;
if(x[p] <= x[i])
break;
swap(x[p] , x[i]);
i = p;
}
}
void siftdown(int n){
int i = 1;
while(1){
int c = 2 * i;
if(c > n){
break;
}
if(c + 1 <= n){
if(x[c + 1] < x[c])
c++;
}
if(x[i] <= x[c])
break;
swap(x[c] , x[i]);
i = c;
}
}
int main()
{
int n;
cin>>n;
for(int i = 1 ; i <= n; i++){
cin>>x[i];
siftup(i);
}
while(n){
cout<<x[1]<<" ";
if(n == 1)
break;
x[1] = x[n--];
siftdown(n);
}
cout<<endl;
return 0;
}
二、用堆和c++模板实现的优先级队列
#include<iostream>
using namespace std;
template <class T>
class priqueue
{
private :
int n , maxsize;
T *x;
void swap(int i , int j){
T t = x[i] ;
x[i] = x[j];
x[j] = t;
}
public:
priqueue(int m){
maxsize = m;
x = new T[maxsize + 1];
n= 0;
}
void insert(T t){
int i ,p;
x[++n] = t;
for(int i = n ; i > 1 && x[p = i / 2] > x[i] ; i = p )
swap(p , i);
}
T extractmin(){
int i , c;
T t = x[1];
x[1] = x[n--];
for(i = 1 ; (c = 2 * i) <= n ; i = c){
if(c + 1 <= n && x[c + 1] < x[c])
c++;
if(x[i] <= x[c] )
break;
swap(c , i);
}
return t;
}
};
int main()
{
priqueue q(100);
int t;
for(int i = 0; i < 10 ; i ++){
cin>>t;
q.insert(t);
}
for(int i = 0; i < 10 ; i ++){
cout<<q.extractmin()<<" ";
}
cout<<endl;
return 0;
}
