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