Tag - 堆和优先队列
一、基础知识
1.1 堆基础知识
堆一般指二叉堆，其实就是首先是个完全二叉树，然后父节点大于子节点或者父节点小于子节点（前者叫大顶堆，后者叫小顶堆）；
堆排序是一种算法，把数据排序；
而优先队列是一种数据结构，是把数据和排序算法封装起来的一种数据结构，而其中的排序算法可以是堆排序（这也是最常用的）。
关于堆和堆排序：请去看B站视频
对于此视频注意一点：
一开始写的heapify函数是从顶部开始向下的，所以会出现最大数在最底下冒不上来的情况，但是up写的第二个build_heap函数包含了heapify并且是从底层开始的，所以能生成堆[微笑]。
其实就是up主说的：
我有提到过一个前提：对一个节点做heapify的时候，必须保证它的所有子树都已经是堆。
所以，在这个前提下，如果要做heapify的节点已经符合“父节点 子节点”的性质，那么这就已经是一个堆了；就没有必要往下走了。
另外，我们的build_heap函数是从最后一个不是叶节点的点开始往前做heapify操作的，所以最后是可以形成一个堆。
我的代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
//heapify()函数，其前提是：对一个节点做heapify的时候，必须保证它的所有子树都 已经 是堆。
void heapify(int tree[],int n,int i){
if(i >= n){
return;
}
int c1 = 2 * i + 1;
int c2 = 2 * i + 2;
int max = i;
if(c1 < n && tree[c1] > tree[max]){
max = c1;
}
if(c2 < n && tree[c2] > tree[max]){
max = c2;
}
if(max != i){
swap(tree[max],tree[i]);
heapify(tree,n,max);
}
}
void build_heap(int tree[],int n){
int last_node = n - 1;
int parent = (last_node - 1) / 2;
for(int i = parent; i >= 0;i--){
heapify(tree,n,i);
}
}
void heap_sort(int tree[],int n){
build_heap(tree,n);
for(int i = n -1;i >= 0;i--){
swap(tree[i],tree[0]);
heapify(tree,i,0);
}
}
int main(){
int tree[] = {2,5,3,1,10,4};
int n = 6;
heap_sort(tree,n);
for(int i = 0;i < n;i++){
cout << tree[i] << endl;
}
}
1.2 优先队列 / C++priority_queue
优先队列数据结构在解决一些高级问题，例如贪心类问题，或者迪杰斯特拉算法，都可以更加方便的解决问题。
在C++中的#include 中有优先队列的数据结构priority_queue<>用法。
请去看这篇文章，通俗易懂
其中需要注意：
1、在C++的一般队列中，使用的是front()函数，而在priority_queue中使用的是top()函数。
2、如果想在priority_queue<>中使用的是pair类型，咋办？请去看:
priority_queue 中存放pair时，自定义排序的写法
struct cmp
{template <typename T, typename U>
bool operator()(T const &left, U const &right)
{
// 以 second 比较。输出结果为 Second 较大的在前, Second 相同时，先进入队列的元素在前。
if (left.second < right.second)
return true;
return false;
}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;