堆与堆排序 堆（二叉堆） 堆排序算法
- 堆（二叉堆）是一种完全二叉树
- 堆有两种类型: 大根堆小根堆
-
两种类型的概念如下：
大根堆（最大堆）：每个结点的值都大于或等于左右孩子结点
小根堆（最小堆）：每个结点的值都小于或等于左右孩子结点
因为比较抽象，所以专门花了两个图表示
那么，什么是完全二叉树呢？
完全二叉树 是 一种除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐的树。
二叉堆的根节点叫做堆顶。
最大堆和最小堆的特点，决定了在最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素。
堆的自我调整
对于二叉堆，如下有几种操作：
插入节点
删除节点
构建二叉堆
这几种操作都是基于堆的自我调整。
下面让我们以最小堆为例，看一看二叉堆是如何进行自我调整的。
1.插入节点
二叉堆的节点插入，插入位置是完全二叉树的最后一个位置。比如我们插入一个新节点，值是 0。
这时候，我们让节点0的它的父节点5做比较，如果0小于5，则让新节点“上浮”，和父节点交换位置。
继续用节点0和父节点3做比较，如果0小于3，则让新节点继续“上浮”。
继续比较，最终让新节点0上浮到了堆顶位置。
2.删除节点
二叉堆的节点删除过程和插入过程正好相反，所删除的是处于堆顶的节点。比如我们删除最小堆的堆顶节点1。
这时候，为了维持完全二叉树的结构，我们把堆的最后一个节点10补到原本堆顶的位置。
接下来我们让移动到堆顶的节点10和它的左右孩子进行比较，如果左右孩子中最小的一个（显然是节点2）比节点10小，那么让节点10“下沉”。
注：小顶堆中进行比较下沉时选择更小的值，大顶堆则选择更大的值
继续让节点10和它的左右孩子做比较，左右孩子中最小的是节点7，由于10大于7，让节点10继续“下沉”。
这样一来，二叉堆重新得到了调整。
3.构建二叉堆
构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次下沉。
我们举一个无序完全二叉树的例子：
首先，我们从最后一个非叶子节点开始，也就是从节点10开始。如果节点10大于它左右孩子中最小的一个，则节点10下沉。
接下来轮到节点3，如果节点3大于它左右孩子中最小的一个，则节点3下沉。
接下来轮到节点1，如果节点1大于它左右孩子中最小的一个，则节点1下沉。事实上节点1小于它的左右孩子，所以不用改变。
接下来轮到节点7，如果节点7大于它左右孩子中最小的一个，则节点7下沉。
节点7继续比较，继续下沉。
这样一来，一颗无序的完全二叉树就构建成了一个最小堆。
数组中，在没有左右指针的情况下，如何定位到一个父节点的左孩子和右孩子呢？
像图中那样，我们可以依靠数组下标来计算。
假设父节点的下标是parent，那么它的左孩子下标就是 2*parent+1；它的右孩子下标就是 2*parent+2 。
比如上面例子中，节点6包含9和10两个孩子，节点6在数组中的下标是3，节点9在数组中的下标是7，节点10在数组中的下标是8。
7 = 3*2+1
8 = 3*2+2
刚好符合规律。
堆排序算法
让我们回顾一下二叉堆和最大堆的特性：
1.二叉堆本质上是一种完全二叉树
2.最大堆的堆顶是整个堆中的最大元素
当我们删除一个最大堆的堆顶（并不是完全删除，而是替换到最后面），经过自我调节，第二大的元素就会被交换上来，成为最大堆的新堆顶。
正如上图所示，当我们删除值为10的堆顶节点，经过调节，值为9的新节点就会顶替上来；当我们删除值为9的堆顶节点，经过调节，值为8的新节点就会顶替上来.......
由于二叉堆的这个特性，我们每一次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。那么我们只要反复删除堆顶，反复调节二叉堆，所得到的集合就成为了一个有序集合，过程如下：
删除节点9，节点8成为新堆顶：
删除节点8，节点7成为新堆顶：
删除节点7，节点6成为新堆顶：
删除节点6，节点5成为新堆顶：
删除节点5，节点4成为新堆顶：
删除节点4，节点3成为新堆顶：
删除节点3，节点2成为新堆顶：
到此为止，我们原本的最大堆已经变成了一个从小到大的有序集合。之前说过二叉堆实际存储在数组当中，数组中的元素排列如下：
由此，我们可以归纳出堆排序算法的步骤：
1. 把无序数组构建成二叉堆。
2. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。
堆排序算法详解+Python实现
下面我们来看下堆排序的思想是怎样的(以大根堆为例)：
- 首先将待排序的数组构造出一个大根堆
- 取出这个大根堆的堆顶节点(最大值)，与堆的最下最右的元素进行交换，然后把剩下的元素再构造出一个大根堆
- 重复第二步，直到这个大根堆的长度为1，此时完成排序。
#沿左,右子节点较大者依次往下调整
def MAX_Heapify( array, HeapSize,root ):#在堆中做结构调整使得父节点的值大于子节点
left = 2*root + 1
right = left + 1
larger = root
if left < HeapSize and array[larger] < array[left]:
larger = left
if right < HeapSize and array[larger] <array[right]:
larger = right
if larger != root:#如果做了堆调整则larger的值等于左节点或者右节点的，这个时候做对调值操作
array[larger],array[root] = array[root],array[larger]
MAX_Heapify(array,HeapSize,larger)
#创建堆
def Build_MAX_Heap( array ):#构造一个堆，将堆中所有数据重新排序
HeapSize = len( array )#将堆的长度单独拿出来方便
for i in range( HeapSize // 2 - 1, -1, -1 ):#从后往前出数
MAX_Heapify( array,HeapSize, i)
#大顶堆排序
def HeapSort( array ):#将根节点取出与最后一位做对调，对前面len-1个节点继续进行对调整过程。
Build_MAX_Heap( array )
#交换堆顶与最后一个结点,再调整堆
for i in range(len(array) - 1, -1, -1 ):
array[0], array[i] = array[i], array[0]
MAX_Heapify(array, i, 0)
return array
a = [ -3, 1, 3, 0, 9, -9, 11, 82, 7 ]
print(HeapSort(a))
二叉堆的节点下沉调整（downAdjust 方法）是堆排序算法的基础，这个调节操作本身的时间复杂度是多少呢？
假设二叉堆总共有n个元素，那么下沉调整的最坏时间复杂度就等同于二叉堆的高度，也就是O（logn）。
我们再来回顾一下堆排序算法的步骤：
1. 把无序数组构建成二叉堆。
2. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。
第一步，把无序数组构建成二叉堆，需要进行n/2次循环。每次循环调用一次 downAdjust 方法，所以第一步的计算规模是 n/2 * logn，时间复杂度 O（nlogn）。
第二步，需要进行n-1次循环。每次循环调用一次 downAdjust 方法，所以第二步的计算规模是 （n-1） * logn ，时间复杂度 O（nlogn）。
两个步骤是并列关系，所以整体的时间复杂度同样是 O（nlogn）。