通過STL建立二叉堆
STL函數庫中的優先隊列底層就是二叉堆的建立priority_queue<>;
簡單的整數的比較直接用預設的比較方法就行了,如果是結構體或者别的類型需要自己手寫比較方法。
int類型的資料預設比較方法是大根堆less
int main()
{
int a[]={5,6,5,1,2,3,8,5,9};
priority_queue<int,vector<int>,greater<int> > pque(a,a+9);//greater從小到大,less為預設從大到小
for(int i=0;i<9;i++)
{
cout<<pque.top();
pque.pop();
}
}
自定義比較類型比較結構體中的資料,手寫friend bool operator比較方法
struct node
{
int data;
int Lchild;
int Rchild;
friend bool operator < (node a,node b)//比較函數的重載
{
return a.data>b.data;//data從小到大排序
}
};
int main()
{
priority_queue<node> que;
for(int i=0;i<5;i++)
{
node n;
cin>>n.data;
que.push(n);
}
for(int i=0;i<5;i++)
{
cout<<que.top().data;
que.pop();
}
}
另外貼一下copy别人的代碼,手動二叉堆的實作
void HeapAdjust(int a[],int s,int m)//一次篩選的過程
{
int rc,j;
rc=a[s];
for(j=2*s;j<=m;j=j*2)//通過循環沿較大的孩子結點向下篩選
{
if(j<m&&a[j]<a[j+1]) j++;//j為較大的記錄的下标
if(rc>a[j]) break;
a[s]=a[j];s=j;
}
a[s]=rc;//插入
}
void HeapSort(int a[],int n)
{
int temp,i,j;
for(i=n/2;i>0;i--)//通過循環初始化頂堆
{
HeapAdjust(a,i,n);
}
for(i=n;i>0;i--)
{
temp=a[1];
a[1]=a[i];
a[i]=temp;//将堆頂記錄與未排序的最後一個記錄交換
HeapAdjust(a,1,i-1);//重新調整為頂堆
}
}
int main()
{
int n,i;
scanf("%d",&n);
int a[n+1];
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
HeapSort(a,n);
for(i=1;i<=n;i++)
{
printf("%d",a[i]);
}
}