堆

概念

堆是一种特殊的完全二叉树
，例如：

可以很明显的发现，示例中的每个父节点都小于它的子节点，符合这个特点的二叉堆叫做最小堆(小根堆)，当然反之就叫最大堆（大根堆）

调整

那么，怎么把一个正常的数组调整为大根堆呢？

基本思路:每一次找到一个点，设其下标为\(i\)，获得它的子节点的下标，设为\(j=2*i\)，首先判断是否有父节点，并判断子节点是否比父节点大，大的话就交换，并把\(j\)上移（即更新为自己的父节点）

void shift(int i, int tot){
	int j = 2 * i;//左边叶节点 
	if (j < tot && a[j + 1] < a[j])
	{
		j++;
	}
	while (i <= (tot >> 1) && a[i] > a[j])
	{
		swap(a[i], a[j]);//调整 
		i = j;
		j << 1;//更新j 
		if (j < tot && a[j + 1] < a[j])
		{
			j++;
		}
	}
}

堆排序

堆排序是一种比较稳定的排序算法，基本保持在\(O(nlogn)\)

基本思路:每一次调整成大顶堆后输出堆顶，并把堆顶和堆末交换，重新调整并把\(tot-1\)（就是把最大的输出后就踢掉，不参与后面的调整）

#include 
using namespace std;
int n, a[10005];
void shift(int i, int tot){
	int j = 2 * i;//左边叶节点 
	if (j < tot && a[j + 1] < a[j])
	{
		j++;
	}
	while (i <= (tot >> 1) && a[i] > a[j])
	{
		swap(a[i], a[j]);//调整 
		i = j;
		j << 1;//更新j 
		if (j < tot && a[j + 1] < a[j])
		{
			j++;
		}
	}
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for (int i = n / 2; i >= 1; i--)
	{
		shift(i, n);//加点并调整 
	}
	for (int i = n; i >= 1; i--)
	{
		cout << a[1] << " ";//输出最大 
		swap(a[1], a[i]);//把排好序的和最后一项换掉 
		shift(1, i - 1);//把排好序的点舍掉，并重新调整 
	}
	return 0;
}

优先队列

优先队列，即\(priority-queue\)，是系统内置的数据结构，就是用堆来实现的，每一次加入数据就向上调整，最大的数永远在堆顶（默认）

操作

//1.定义
priority_queue, greater > q//小顶堆
priority_queue, less > q//大顶堆
//2.加入元素
q.push(元素);
//3.推出元素
q.pop();
//4.堆顶元素
q.top();
//5.堆是否为空
q.empty();
  

优先队列排序

#include 
using namespace std;
priority_queue, greater > q; 
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int in;
		cin >> in;
		q.push(in);
	}
	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();	
	} 
	return 0;
}