堆通常是一个数组对象，可以（完全）看成一棵树。并且总是满足如下规则：堆是一棵完全二叉树，节点总是大于（或小于）它的子节点。因此，根据第二个特点，二叉堆分为大顶堆（或称为最大堆）和小顶堆（或称为最小堆）。上图中，12是大顶堆，34是小顶堆。判断是否为堆的条件：“节点序列在从根节点到任意节点的路径上的顺序！大顶堆和小顶堆决定序列是顺序还是逆序！”Python没有提供“堆”数据类型，它直接把列表当作堆。Python提供的heapq包中有一些函数，提供了执行堆操作的工具函数>>>importtheapq>>>heapq.__all__['heappush','heappop','heapify','heapreplace','merge','nlargest','nsmallest','heappushpop']堆排序向堆中插入一个元素后，我们需要再次调整以满足堆的特性。这个过程称为堆化。那么堆排序的基本思想是什么？将待排序序列构建成堆H[0...n-1]，根据（升序和降序要求）选择大顶堆或小顶堆；值）和堆的末尾；按照节点的路径，向上或向下，比较，然后交换，目的是将新数组的顶部数据调整到相应的位置；下面的例子（资源来自王政算法），比如将数据22添加到上面的大顶堆中。堆很简单，就是按照节点的路径，往上或者往下走，比较，然后交换。堆排序的删除操作一般是指堆顶元素。当我们删除堆顶元素时，需要把第二大的元素放到堆顶，而第二大的元素肯定会出现在左右子节点中。然后我们迭代删除第二大节点，以此类推，直到删除叶节点。但是这样会造成一个空数组的问题。所以，这里还有一个技巧，就是在删除堆顶元素的时候，不能直接删除，而是用顶元素和末元素交换一下，然后根据堆的特点调整堆直到满足条件。排序过程就是每次将待排序序列的长度减1，然后执行这两个步骤。以下是Python中heapq模块实现的堆排序的简单代码。fromheapqimporttheappop,heappushdefheap_sort(array):heap=[]forelementinarray:heappush(heap,element)ordered=[]whileheap:ordered.append(heappop(heap))returnorderedarray=[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模块，需要了解heapsortingforpushsorting堆构建过程。将数组就地构建到堆中。在不求助于另一个数组的情况下对原始数组进行操作。关于构建堆的过程，有两种思考方式。建堆的第一个思路的处理过程是从前向后处理数组数据，每条数据插入堆时，都是从下往上堆的。第二种实现思路是数组从后往前处理，每条数据从上到下堆起来。补充：使用层级遍历（遍历方式也包括前中后）映射到数组后，假设树或子树的根节点为arr[root]，则其对应的子节点为arr[root*2+1]，到达[根*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
