【算法/数据结构】堆排序/优先队列

堆 每个父节点都大于其子节点称为大根堆 小于则称为小根堆

堆排序 维护$n$个元素的初始大根堆或小根堆，以大根堆为例，每次取出堆的最大元素R[1]放到堆末尾R[n]，然后对$1...n-1$进行大根堆性质的维护，即$sift$操作，重复上述操作$n-1$次 最后得到的序列即为按照递增顺序排好的序列。

代码如下：

#include <iostream>

using namespace std;

void sift(int R[], int low, int high);
void heap_sort(int R[], int n);

int main()
{
    int a[100];
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
    }
    heap_sort(a,n);
    
    for(int i = 1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }

}

void sift(int R[], int low, int high)
{
    int i = low, j = 2*i; //从下往上调整
    // 每次sift都能浮出一个该次sift的最大值
    int tmp = R[i];
    while(j<=high)
    {
        if(j<high and R[j+1]>R[j])
        {
            j++; // 选出儿子中较大值用于备用上浮
        }
        if(tmp < R[j]) // 当前父节点小于当前上浮结点即可上浮
        {
            R[i] = R[j];
            i = j; //缩小上浮范围
            j = 2*i;
        }else break;
    }
    R[i] = tmp;
}

void heap_sort(int R[], int n)
{
    int i; int tmp;
    for(i=n/2;i>=1;i--)
    {
        sift(R,i,n); // 从最后一个结点的父节点开始上浮
    }
    for(i=n;i>=2;i--)
    {
        tmp = R[1];
        R[1] = R[i]; // 将当前大根堆的最大结点取出，与末尾元素交换 用于形成递增序列
        R[i] = tmp;
        sift(R,1,i-1); // 最后一个元素不用上浮 用于形成递增序列
    }
}

优先队列(priority_queue) 位于$$中，该优先队列底层使用堆维护，默认为递减序列。 递增序列见代码示例。

#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

priority_queue<int,vector<int>,greater<int>> q;

int main()
{
    int n ;
    cin>>n;
    int tmp;
    for(int i = 1; i <= n;i++)
    {
        cin>>tmp;
        q.emplace(tmp);
    }
    for(int i =1 ;i<=n;i++)
    {
        cout<<q.top()<<" ";
        q.pop();
    }
}