数据结构 堆和
priority_queue

一、堆的定义

堆（heap），是⼀棵有着特殊性质的完全⼆叉树，可以⽤来实现优先级队列（priorityqueue）。
堆需要满⾜以下性质：
1. 是⼀棵完全⼆叉树；
2. 对于树中每个结点，如果存在⼦树，那么该结点的权值⼤于等于（或⼩于等于）⼦树中所有结点
的权值。
如果根结点⼤于等于⼦树结点的权值，称为⼤根堆；反之，称为⼩根堆。

二、堆的存储

由于堆是⼀个完全⼆叉树，因此可以⽤⼀个数组来存储。（用到的是二叉树的顺序存储）

结点下标为i ：
• 如果⽗存在，⽗下标为i/2 ；
• 如果左孩⼦存在，左孩⼦下标为i × 2 ；
• 如果右孩⼦存在，右孩⼦下标为i × 2 + 1 。

三、核⼼操作

堆中的所有运算，⽐如建堆，向堆中插⼊元素以及删除元素等，都是基于堆中的两个核⼼操作实现的-
--向上调整算法以及向下调整算法。
因此，在实现堆之前，先来掌握两种核⼼操作。
注意：以下所有操作都默认堆是⼀个⼤根堆，⼩根堆的原理反着来即可。

向上调整算法

算法流程：
1. 与⽗结点的权值作⽐较，如果⽐它⼤，就与⽗亲交换；
2. 交换完之后，重复1 操作，直到⽐⽗亲⼩，或者换到根节点的位置。

int n; // 标记堆的⼤⼩ 
int heap[N]; // 存堆 - 默认是⼀⼤根堆 
// 向上调整算法 
void up(int child)
{int parent = child / 2;// 如果⽗结点存在，并且权值⽐⽗结点⼤ while(parent >= 1 && heap[child] > heap[parent]){swap(heap[child], heap[parent]);// 交换之后，修改下次调整的⽗⼦关系，注意顺序不能颠倒 child = parent;parent = child / 2;}
}

时间复杂度：
最差情况需要⾛⼀个树⾼，因此时间复杂度为log N

向下调整算法

算法流程：
1. 找出左右⼉⼦中权值最⼤的那个，如果⽐它⼩，就与其交换；
2. 交换完之后，重复1 操作，直到⽐⼉⼦结点的权值都⼤，或者换到叶节点的位置。

int n; // 标记堆的⼤⼩ 
int heap[N]; // 存堆 - 默认是⼀⼤根堆 
// 向下调整算法 
void down(int parent)
{int child = parent * 2;while(child <= n) // 如果还有孩⼦ {// 找出两个孩⼦谁是最⼤的 if(child + 1 <= n && heap[child + 1] > heap[child]) child++;// 最⼤的孩⼦都⽐我⼩，说明是⼀个合法的堆 if(heap[child] <= heap[parent]) return;swap(heap[child], heap[parent]);// 交换之后，修改下次调整的⽗⼦关系，注意顺序不能颠倒 parent = child;child = parent * 2;}
}

时间复杂度：
最差情况需要⾛⼀个树⾼，因此时间复杂度为log N 。

四、priority_queue

1、优先级队列

普通的队列是⼀种先进先出的数据结构，即元素插⼊在队尾，⽽元素删除在队头。
⽽在优先级队列中，元素被赋予优先级，当插⼊元素时，同样是在队尾，但是会根据优先级进⾏位置调整，优先级越⾼，调整后的位置越靠近队头；同样的，删除元素也是根据优先级进⾏，优先级最⾼的元素（队头）最先被删除。
其实可以认为，优先级队列就是堆实现的⼀个数据结构。
priority_queue就是C++提供的，已经实现好的优先级队列，底层实现就是⼀个堆结构。在算法竞赛中，如果是需要使⽤堆的题⽬，⼀般就直接⽤现成的priority_queue，很少⼿写⼀个堆，因为省事~

2、创建priority_queue-初阶

优先级队列的创建结果有很多种，因为需要根据实际需求，可能会创建出来各种各样的堆：
1. 简单内置类型的⼤根堆或⼩根堆：⽐如存储int 类型的⼤根堆或⼩根堆；
2. 存储字符串的⼤根堆或⼩根堆；
3. 存储⾃定义类型的⼤根堆或⼩根堆：⽐如堆⾥⾯的数据是⼀个结构体。
关于每⼀种创建结果，都需要有与之对应的写法。在初阶阶段，先⽤简单的int 类型建堆，重点
学习priority_queue的⽤法。

注意： priority_queue 包含在queue 这个头⽂件中。

#include <iostream>
#include <vector>
#include <queue> // 优先级队列的头⽂件在 queue ⾥⾯ 
using namespace std;
// 优先级队列的使⽤ 
void test1()
{int a[10] = {1, 41, 23, 10, 11, 2, -1, 99, 14, 0};priority_queue<int> heap; // 默认写法下，是⼀个⼤根堆 
}

size/empty
1. size ：返回元素的个数。
2. empty ：返回优先级队列是否为空

push
• 往优先级队列⾥⾯添加⼀个元素。
时间复杂度：因为底层是⼀个堆结构，所以时间复杂度为O(log N) 。
pop
• 删除优先级最⾼的元素。
时间复杂度：因为底层是⼀个堆结构，所以时间复杂度为O(log N) 。
top
• 获取优先级最⾼的元素。
时间复杂度：O(1) 。

3、创建priority_queue-进阶

以int 类型为例，分
别创建⼤根堆和⼩根堆。

#include <iostream>
#include <vector>
#include <queue> // 优先级队列的头⽂件在 queue ⾥⾯ 
using namespace std;
// 内置类型 
void test()
{int a[10] = {1, 41, 23, 10, 11, 2, -1, 99, 14, 0};// ⼤根堆 priority_queue<int> heap1; // 默认就是⼤根堆 // priority_queue<数据类型， 存数据的结构， 数据之间的⽐较⽅式> priority_queue<int, vector<int>, less<int>> heap2; // 也是⼤根堆 // ⼩根堆 priority_queue<int, vector<int>, greater<int>> heap3; // ⼩根堆 // 测试 for(auto x : a){heap1.push(x);heap2.push(x);heap3.push(x);}while(heap1.size()){cout << heap1.top() << " "; // 获取堆顶元素的值 heap1.pop(); // 删除元素 }cout << endl;while(heap2.size()){cout << heap2.top() << " "; // 获取堆顶元素的值 heap2.pop(); // 删除元素 }cout << endl;while(heap3.size()){cout << heap3.top() << " "; // 获取堆顶元素的值 heap3.pop(); // 删除元素 }cout << endl;
}
int main()
{test();return 0;
}

priority_queue<数据类型， 存数据的结构， 数据之间的⽐较⽅式>

greater是小根堆。