完全二叉树优先队列法

1、首先了解堆是什么
堆是一种数据结构，一种叫做完全二叉树的数据结构。

2、堆的性质
这里我们用到两种堆，其实也算是一种。

大顶堆：每个节点的值都大于或者等于它的左右子节点的值。

小顶堆：每个节点的值都小于或者等于它的左右子节点的值。

如上所示，就是两种堆。

如果我们把这种逻辑结构映射到数组中，就是下边这样

9 5 8 2 3 4 7 1
1 3 5 4 2 8 9 7
这个数组arr逻辑上就是一个堆。

从这里我们可以得出以下性质（重点）

对于大顶堆：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

对于小顶堆：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

熟悉了之前所学的内容；我们可以深入探讨堆排序的基本思想。

堆排序的基本思想是：

构建一个大顶堆结构，并依据其特点可知该结构顶端节点即为整个序列的最大值；

首先将初始节点与最后一个节点进行交换；接着利用这些节点重新构建一个新的最大堆结构。

3、依次重复步骤2的操作，在构造第一个最大