优先队列及堆排序
最后更新于：2022-04-02 04:11:23
[TOC]
## 优先队列及堆排序
优先队列是一种能完成以下任务的队列：插入一个数值，取出最小或最大的数值（获取数值，并且删除）。
优先队列可以用二叉树来实现，我们称这种结构为二叉堆
最小堆和最大堆是二叉堆的一种，是一棵完全二叉树（一种平衡树）。
最小堆的性质：
1. 父节点的值都小于左右儿子节点。
2. 这是一个递归的性质。
最大堆的性质：
1. 父节点的值都大于左右儿子节点。
2. 这是一个递归的性质。
最大堆和最小堆实现方式一样，只不过根节点一个是最大的，一个是最小的
### 最大堆特征
最大堆实现细节(两个操作)：
1. push：向堆中插入数据时，首先在堆的末尾插入数据，如果该数据比父亲节点还大，那么交换，然后不断向上提升，直到没有大小颠倒为止。
2. pop：从堆中删除最大值时，首先把最后一个值复制到根节点上，并且删除最后一个数值，然后和儿子节点比较，如果值小于儿子，与儿子节点交换，然后不断向下交换， 直到没有大小颠倒为止。在向下交换过程中，如果有两个子儿子都大于自己，就选择较大的。
最大堆有两个核心操作，一个是上浮，一个是下沉，分别对应`push`和`pop`
';