堆通常是一个能够被看做一棵树(彻底)的数组目标。且总是满意以下规矩：

堆是一棵彻底二叉树

节点总是大于(或小于)它的孩子节点。

因而，依据第二个特性，就把二叉堆分为大顶堆(或叫最大堆)，和小顶堆(或叫最小堆)。

在上图中，1 2 是大顶堆 ，3 4 是小顶堆。判别是不是堆的条件：「从根结点到恣意结点途径上结点序列的有序性!大顶堆和小顶堆判别序列是次序仍是逆序!」

Python并没有供给“堆”这种数据类型，它是直接把列表当成堆处理的。Python供给的heapq包中有一些函数，供给履行堆操作的东西函数

>>>importheapq
>>>heapq.__all__
['heappush','heappop','heapify','heapreplace','merge','nlargest','nsmallest','heappushpop']

堆排序

往堆中刺进一个元素后，咱们就需求进行调整，让其从头满意堆的特性，这个进程叫做堆化(heapify)。

那么堆排序的基本思路是怎么样的呢?

1. 将待排序序列构建成一个堆 H[0……n-1]，依据(升序降序需求)挑选大顶堆或小顶堆;
2. 把堆首(最大值)和堆尾交流;
3. 顺着节点地点的途径，向上或许向下，比照，然后交流，意图是把新的数组顶端数据调整到相应方位;

下面举个比方(资源来自王争算法)，比方在上面的大顶堆中增加数据22。

堆化十分简略，便是顺着节点地点的途径，向上或许向下，比照，然后交流。

堆排序的删去操作，这儿一般指的是堆顶元素，当咱们删去堆顶元素之后，就需求把第二大的元素放到堆顶，那第二大元素肯定会出现在左右子节点中。

然后咱们再迭代地删去第二大节点，以此类推，直到叶子节点被删去。可是这样会发生一个数组空泛的问题。

因而，这儿面又个技巧，便是删去堆顶元素的时分，不能直接删去，要用堆顶元素和最终一个元素做交流，然后依据堆的特色调整堆，直到满意条件。

排序的进程便是每次待排序的序列长度减去1再履行这两步。

下面给出经过Python中的heapq模块完成的堆排序简略代码。

fromheapqimportheappop,heappush
defheap_sort(array):
heap=[]
forelementinarray:
heappush(heap,element)
ordered=[]
whileheap:
ordered.append(heappop(heap))
returnordered
array=[13,21,15,5,26,4,17,18,24,2]
print(heap_sort(array))
#[2,4,5,13,15,17,18,21,24,26]

假如不运用heapq模块，关于推排序需求了解堆排序中的建堆进程。

将数组原地建成一个堆。不凭借另一个数组，就在原数组上操作。建堆的进程，有两种思路。

第一种建堆思路的处理进程是早年往后处理数组数据，而且每个数据刺进堆中时，都是从下往上堆化。而第二种完成思路，是从后往前处理数组，而且每个数据都是从上往下堆化。

• 弥补：使用层序遍历(遍历方法还有前中后)映射到数组后，假定树或子树的根节点为arr[root],则其对应的子节点分别为arr[root*2+1],arr[root*2+2]。

也便是假如节点的下标是 i，那左子节点的下标便是 2∗i+1，右子节点的下标便是 2∗i+2，父节点的下标便是 。

defheap_sort(array):
n=len(array)
#从尾部开始建堆，这样确保子节点有序
foriinrange((n-1)//2,-1,-1):
_shift(array,n,i)
#顺次把堆顶元素交流到最终，重建堆顶（堆不包括刚交流的最大元素）
foriinrange(n-1,0,-1):
array[0],array[i]=array[i],array[0]
_shift(array,i,0)
returnarray
#重建堆顶元素n：堆元素个数，i：堆建顶方位
def_shift(array,n,i):
#假如没有子节点，直接回来
ifi*2+1>=n:
return
#取最大子节点方位
maxsub=i*2+2ifi*2+2<nandarray[i*2+1]<=array[i*2+2]elsei*2+1
#假如节点小于最大子节点，交流元素，递归以子节点为堆顶重建
ifarray[i]<array[maxsub]:
array[i],array[maxsub]=array[maxsub],array[i]
_shift(array,n,maxsub)
if__name__=='__main__':
array=[13,21,15,5,26,4,17,18,24,2]
print(heap_sort(array))
#[2,4,5,13,15,17,18,21,24,26]

堆排序不是稳定的排序算法，由于在排序的进程，存在将堆的最终一个节点跟堆顶节点交流的操作，所以就有或许改动值相同数据的原始相对次序。堆排序全体的时刻复杂度是O(nlogn) 。

参考资料 https://github.com/MaoliRUNsen/runsenlearnpy100