[Day16]程序菜鸟自学C++资料结构演算法 – 优先伫列Priority Queue和堆积Heap

前言：在第11天的时候我们有讨论到伫列，今天就是来把之前的坑给补上的，先前没有提到的就是等等要介绍的「优先伫列」，因为优先伫列和堆积有些关系，所以放在这篇一起讲。

优先伫列(Priority Queue)：

稍微帮大家复习一下，如果忘记的可以去看看之前的文章。

普通的伫列是一种先进先出的数据结构，元素在伫列尾端被加入，而删除和查找都是从伫列前端执行。
而在优先伫列中，元素被赋予优先级，当访问到元素时，具有最高优先级的元素会最先被删除，就像是VIP在能有优先进场的资格一样，而优先伫列通常都会利用「堆积」来完成。

程序实作：用VS2019内部的伫列方法简单实作一下，之後会再完整的练习。

优先伫列的五种实现方式：

1. 无序数组
2. 有序数组
3. 链接串列(有序或无序都可)
4. 二元排序树或平衡二元树(非本次重点暂不讨论)
5. 堆积(最有效率)

快速介绍完了优先堆积，接着就要进入今天的重头戏。

堆积(Heap)：

堆积有很多种类，今天就只介绍最基本的最大堆积(Max-Heap)和最小堆积(Min-Heap)。

是不是觉得非常眼熟？堆积其实是完整二元树的一种，只要满足如上图的条件( 最大或最小的元素在树跟，其余元素由小到大或由大到小排列 )，完整二元树就可以称作堆积。

最大堆积：树跟为最大值，所有节点值均不小於它的子节点的值。
最小堆积：树跟为最小值，所有节点值均不大於它的子节点的值。

堆积的特性也很适合使用在排序，称为堆积排序法，等之後进入演算法的环节在充分介绍。

堆积操作概念：
•由上而下，从树根开始与其子节点开始比较，若前者较大则不用交换，反之，则要交换；以符合父节点大於子节点的规则。
•由下而上，从树葉开始与其父节点开始比较，若後者较大则不用交换，反之，则要交换；以符合父节点大於子节点规则。

这类方法子节点(父节点)先比，找出最大者再与父节点(子节点)交换，这样就只要交换一次就行，所以如果有交换节点的情况发生，这类方法是最推荐的。

本日小结：优先伫列和堆积的概念说明就先到这里结束，明天要来实际创建堆积，并尝试时做向上和向下的调整，如果可以希望还能讲解一下AMC程序竞赛的题目。今天稍微轻松一点，明天还要继续努力(*•̀ㅂ•́)و

#include <queue>
#include <iostream>
using namespace std;

int main() {
	priority_queue<int> q;
	q.push(5);
	q.push(9);
	q.push(14);
	q.push(3);
	q.push(27);
	q.push(1);
	cout << "伫列元素各数" << q.size() << endl;
	while (!q.empty()) {
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl;
	return 0;
}