手写堆priority_queue优先队列
堆常见有两种实现方式:
第一种是数组模拟
第二种是用STL中priority_queue优先队列
各自优缺点:
1. 由于优先队列无法删除和修改非队头元素,所以如果有以上需求需要手写堆。
2. 优先队列相对数组模拟速度要慢一些。
3. 如果数据类型比较复杂,建议优先队列,如Dijkstra堆优化等。
手写堆(数组模拟):
用数组heap模拟堆,下标 1 为根节点下标(此处不要用 0 为根节点,因为 0 的左儿子需要特判 0*2=0.....),size为尾部指针,同时为元素数量。
1. up方法:将某元素向上调整到不能调整为止(递归)
2. down操作,将某元素向下调整到不能调整为止(需要判断是否比左右儿子大,并且跟更小的那个儿子交换位置,然后继续递归)
3.对于删除某个元素,因为删除非尾部元素较难实现,但是尾部元素可以通过 size-1 的方式快速实现。
所以用尾部元素替代所要删除的元素,然后删掉尾部元素,并且调整尾部元素的位置(此处为原尾部元素)
//数组模拟堆
//此处为小根堆,即二叉树从上到下递减,根节点最小
int size; //数组尾部指针,同时为数组中元素数量
int heap[N] //heap数组模拟堆
void up(int x){ //up操作,将某元素向上调整到不能调整为止
if(h[x]<h[x/2]) swap(h[x],h[x/2]),up(x/2);
}
void down(int x){ //down操作,将某元素向下调整到不能调整为止
int t=x;
if(x*2<=s&&h[x*2]<h[t]) t=x*2;
if(x*2+1<=s&&h[x*2+1]<h[t]) t=x*2+1;
if(x!=t) swap(h[x],h[t]),down(t);
}
1. 插入元素 heap[++size]=x,up(x)
2. 获取堆顶元素 heap[1]
3. 删除堆顶元素 heap[1]=heap[size],size--,down(1)
4. 删除任意元素 heap[k]=heap[size],size--,down(k),up(k)
5. 修改任意元素 heap[k]=x,down(k),up(k)
优先队列priority_queue
1. 头文件<queue>
2.定义一个priority_queue类型的变量。可以在定义时指定元素类型和底层容器类型,例如
priority_queue<int, vector<int>, greater<int>> q1; // 从小到大排序(小根堆)
priority_queue<string, vector<string>, less<string>> q2; // 从大到小排序(大根堆)
priority_queue<string>q3 //大根堆可以省略容器和排序方式 q2=q3
3. 函数操作
q.push(x) //插入元素
q.top() //返回队首元素
q.pop() //弹出队首元素
q.empty() //非空返回false,已空返回true
q.size() //返回元素数量
priority_queue 也没有迭代器,因此访问元素的唯一方式是遍历容器,通过不断移除访问过的元素,去访问下一个元素。