堆分为大根堆小根堆
本文以大根堆为例


原理

一个数组存储整个序列

下标为k的数左孩子为2k+1, 右孩子为2k+2

保持每个子树的根值大于它孩子的值

对每一个非叶子节点进行排序
将整棵树的根节点(序列最大值)放到正在进行排序的末尾i
对0~i-1的序列继续排序
数组模拟的完全二叉树


模版

手动模拟

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

void adjust(int arr[], int len, int index)
{
    int left = 2*index + 1;
    int right = 2*index + 2;
    int maxIdx = index;
    if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
    if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;  // maxIdx是3个数中最大数的下标
    if(maxIdx != index)                 // 如果maxIdx的值有更新
    {
        swap(arr[maxIdx], arr[index]);
        adjust(arr, len, maxIdx);       // 递归调整其他不满足堆性质的部分
    }

}
void heapSort(int arr[], int size)
{
    for(int i=size/2 - 1; i >= 0; i--)  // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
    {
        adjust(arr, size, i);
    }
    for(int i = size - 1; i >= 1; i--)
    {
        swap(arr[0], arr[i]);           // 将当前最大的放置到数组末尾
        adjust(arr, i, 0);              // 将未完成排序的部分继续进行堆排序
    }
}

int main()
{
    int array[8] = {8, 1, 14, 3, 21, 5, 7, 10};
    heapSort(array, 8);
    for(int i=0; i<8; ++i)
    	cout<<array[i]<<' ';
    return 0;
}

STL

#include<cstdio>
#include<queue>
using namespace std;
int n,x,ans;
priority_queue<int, vector<int>, greater<int> >q;
int main()
{
	int n, x, ans = 0;
    scanf("%d", &n); 
    for(int i=1;i<=n;i++) 
	{
		scanf("%d", &x);
		q.push(x);
	}
    while(q.size()>=2)
	{
        int a=q.top(); 
		q.pop();
        int b=q.top(); 
		q.pop();
        ans += a+b;
        q.push(a+b);
    }
    printf("%d", ans);
    return 0;
}

代码题目传送门

注意

  • 不使用#include<vector>头文件
  • greater是序列升序,less是序列降序
  • 声明语句最后的两个 > > 要有一个空格