堆、优先队列、堆排序

堆：

定义：

必须是一个完全二叉树（完全二叉树：完全二叉树只允许最后一行不为满，且最后一行必须从左往右排序，最后一行元素之间不可以有间隔）

 堆序性：

大根堆：每个父节点元素都要大于子节点元素

小根堆：每个父节点元素都要小于子节点元素

 堆的存储：

首先按照层序遍历的顺序来给结点编号（从上到下从左到右）把这些编号对应到一个数组的下标，把相应的元素存入数组中（二叉树的序号和结点有着相应的规律，之前有讲）

堆的基本操作：

下滤：将根点与其最大子节点进行比较，如果小于其最大子节点则进行交换，持续比较交换直到该元素大于其子节点为止或者移动到底部为止（主要用于新元素的加入，复杂度O(logN）可以重新构建成堆）

上滤：将最后一个节点与父节点进行比较，如果大于其父节点则进行交换直到无法上移为止

自顶向下建堆法：将新元素放到堆的最后一位，然后对其进行上滤操作，直到所有元素插入后完成建堆时间复杂度为O(N logN)

自下而上建堆法：将元素先调整成堆，然后再对父节点进行下滤操作，直到根结点操作完毕，这种建堆方法的时间复杂度为O(N)

优先队列：

弹出最小元素的队列可以用小根堆来实现，因为小根堆的根结点本来就是最小元素，所以直接弹出根结点即可完成弹出操作将最后一个元素放到根结点进行下滤操作即可，插入直接上滤即可

堆排序：

将大根堆结点按层序遍历不断弹出即为正序，

反之为倒叙

过程：

1.建堆，以大根堆为例，倒着检查第一个非叶结点，即n/2是否大于其左右结点，否则与左右节点中较大的数进行交换，并不断向下进行比较（直到大于等于其左右结点或者已经到叶结点了）

2.排序，不断检查更新最后的数，然后将放好的数隐藏掉