数据结构堆和
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是小根堆。