堆和STL —— priority_queue 【复习笔记】

1. 堆

1.1 堆的定义

堆是一棵特殊的完全二叉树，可以实现优先级队列(priority queue)，堆中每个结点，如果存在子树，那结点的权值要大于等于（小于等于）子树的所有结点的权值

堆可以分为大根堆：结点权值大于等于子树所有结点的权值

小根堆：结点权值小于等于子树所有结点的权值

1.2 堆的存储

因为堆是一棵完全二叉树，而对于完全二叉树和满二叉树，可以使用数组来顺序存储。（二叉树的概念和静态实现【复习笔记】-CSDN博客）

如果结点下标为 i （根结点从编号1开始）：

（如果下列结点存在）

1. 父节点下标为 i / 2;

2. 左孩子下标为 i * 2;

3. 右孩子下标为 i * 2 + 1；

堆的逻辑实现是完全二叉树，但存储实现是数组，如果要实现堆结构，要对数组进行一些调整

1.3 调整方法

1.3.1 向下调整法

实现方法：1. 新添加的叶子节点和父节点权值比较，如果比它大（小），就交换

2. 交换后，重复过程1，直到节点比父亲节点权值小（大），或到达根节点的位置

#include<iostream>
using namespace std;int n;
const int N = 1e6;
int heap[N];//大根堆向上调整(小根堆改变大小判断即可)
void up(int child)
{int father = child / 2;//父节点存在，节点权值大于父节点while (father >= 1 && heap[father] < heap[child]){swap(heap[father], heap[child]);//调整关系，重复过程child = father;father = child;}
}//因为比较次数最差为树高，时间复杂度为O(log N)

1.3.2 向下调整法

实现方法：1. 找到左、右孩子中权值最大（小）的那个，如果比自己权值小，就交换

2. 重复过程1，直到换到叶子节点，或孩子节点的权值都比自己权值小（大）

#include<iostream>
using namespace std;int n;//标记堆大小
const int N = 1e6 + 10;
int heap[N];//大根堆向下调整
void down(int father)
{//找到左孩子节点int child = father * 2;//如果左孩子节点存在while (child<=n){//找到孩子节点中最大的if (child+1 <=n && heap[child] < heap[child + 1]) child += 1;if (heap[child] <= heap[father]) return;swap(heap[child], heap[father]);//重复该过程father = child;child = father * 2;}
}//因为比较次数最差为树高，时间复杂度为O(log N)

1.4 堆的实现

以下实现只是为了对堆进行模拟，会存在一些bug：堆为空还删除元素的情况未考虑（这需要自己判断是否堆为空，再进行删除）......

#include<iostream>
using namespace std;const int N = 1e6 + 10;
int n;
int heap[N];//默认大根堆void up(int child)
{int parent = child / 2;while (parent >= 1 && heap[child] > heap[parent]){swap(heap[parent], heap[child]);child = parent;parent = child / 2;}
}void down(int parent)
{int child = parent * 2;while (child <= n){if (child + 1 <= n && heap[child] < heap[child + 1])child++;if (heap[child] <= heap[parent]) return;swap(heap[child], heap[parent]);parent = child;child = parent * 2;}
}//插入，时间复杂度O(log N)
void push(int x)
{//根节点编号从1开始heap[++n] = x;//向上调整up(x);
}//删除，时间复杂度O(log N)
void pop()
{//先交换删除堆顶元素，再调整swap(heap[n--], heap[1]);//向下调整down(1);
}//返回堆顶元素，时间复杂度O(1)
int top()
{return heap[1];
}//返回堆大小，时间复杂度O(1)
int size()
{return n;
}//测试
int main()
{for (int i = 1; i <= 5; i++){push(i);}while (size()){cout << top() << " ";pop();}return 0;
}

2. priority_queue

优先级队列：元数被赋予优先级（权重），当在队尾插入元素时，会根据优先级进行比较调位；删除元素，也会根据优先级进行调位，队头（堆顶）先删除

（可以认为，优先级队列就是堆实现的数据结构）

2.1 内置类型的堆的创建

#include<iostream>
#include<queue>//优先级队列的头文件
using namespace std;int main()
{//默认创建一个大根堆priority_queue<int> heap;//插入，时间复杂度O(log N)for (int i = 1; i <= 5; i++){heap.push(i);}//返回元素个数,时间复杂度O(1)cout << heap.size() << endl;//返回优先级最高元素，时间复杂度O(1)cout << heap.top() << endl;//删除，时间复杂度O(log N)for (int i = 1; i <= 5; i++){heap.pop();}//返回堆是否为空，时间复杂度O(log N)cout << heap.empty() << endl;return 0;}

2.2 结构体类型

优先级队列的原始创建：

#include<iostream>
#include<queue>//优先级队列的头文件
using namespace std;//priority_queu<数据类型，存储数据的结构，数据的比较方式>
//大根堆的比较为小于
priority_queue<int, vector<int>, less<int>> heap1;
//小根堆的比较为大于
priority_queue<int, vector<int>, greater<int>> heap2;//对于内置类型，可以直接传递

对于非内置类型如结构体：

1. 可以在结构体中重载 < 比较运算符

2. 可以传递比较函数

#include<iostream>
#include<queue>//优先级队列的头文件
using namespace std;struct node
{int a, b, c;//定义小根堆，大于比较，以b为比较基准/*bool operator < (const node& x)const{return b > x.b;}*///定义大根堆，小于比较，以b为比较基准bool operator < (const node& x)const{return b < x.b;}
};void test()
{priority_queue<node> heap;for (int i = 1; i <= 5; i++){heap.push({i, i, i});}while (heap.size()){auto e = heap.top(); heap.pop();cout << e.b << " ";}cout << endl;
}
int main()
{test();return 0;
}