Binary Heap的定义

这个堆又分为最小堆和最大堆，所以这里直接用Binary Heap来代替，叫二分堆（？）

Binary heap是一个完整的二叉树,并且满足堆的排序性质，即每次都可以pop出来最大或者最小值，由于这种性质，我们也将堆称作priority queue

完整二叉树说的是除了最后行,其他的分支都被填满的树

根据堆的排序标准,它主要可以被分为两种:

这里我们只用最小堆minheap来举例。

Array Implementation

在返回堆代表的序列时，是按照遍历每一层的顺序，因此最小堆结构的整体并不是有序的结构，只可能是部分有序，且第一项是最小值。

往最小堆中插入一个数字，是先将该数字放在最小堆的末尾，然后和它的parent相比较，如果大于它的parent那就正好不用移动，如果小于它的parent那么就将它和parent换位置，直到到达符合小于parent的位置。

删除最小值的时候是先将root（最上面的parent，也就是我们的最小值）和堆的最后一位换位置，然后把它换下来。换在最上面的值会和左右两边的parent进行比较，然后往下放，直到换到一个合适的位置（符合最小堆性质）。

就是按照刚才delete的顺序，不听去掉root的值然后进行排序，最差的时长是 O(nlogn)

常用的函数

注意heapq里面是按照最小堆来进行整合的，所以我们每次pop出来的都是最小值。

heapq.heappush(*heap*, *item*)

Push the value item onto the heap, maintaining the heap invariant.
heapq.heappop(*heap*)

Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].
heapq.heapify(*x*)

Transform list x into a heap, in-place, in linear time.

如果我们想使用最大堆的话，可以再输入堆的数字前面加上负号，然后输出的时候再赋予负号

Python中的heapq包也同样有

heapq._heapify_max(heap) 这样的函数，但是目测，如果使用最大堆的话，需要一直使用隐函数的最大堆max的函数，不然的话，heap的顺序就会乱掉。

比如一开始用heapq._heapify_max(nums) 排列了序列，然后再 heapq.heappop(nums) 这样的话输出的是最大值，且pop之后的序列的最小值会换上来，所以中间的序列顺序会被打乱。