【数据结构 堆和优先权队列】

堆概念和存储表示

优先权队列是基于堆结构的一种应用
堆的逻辑结构是完全二叉树（应用场景：新元素加入无关紧要，但每次取出元素具有最高优先级）
堆的定义：逻辑结构来看，是一棵包含n个结点的完全二叉树根结点叫堆顶
最小堆：每个结点小于或等于其孩子结点，堆顶最小

最大堆：每个结点大于或等于其孩子结点，堆顶最大

堆的顺序存储：一维数组

判断是否为最大堆或者最小堆：看是否满足定义
假设使用线性表 则复杂度为O(n)
使用堆和优先权队列

堆的运算

优先权队列

定义：元素加入无关紧要，取出元素只取具有最高优先权级别的元素，称为优先权队列

1. 每个元素都有优先权，且可以比较大小
2. 元素按照优先权高低顺序依次出队，而不是按元素进入队列的先后顺序
   传统队列可以看作一种特殊的优先权队列，假设进入队列的优先权时间越长优先权越高