Python堆排序算法

堆排序,就像它的名字一样,利用了堆的特性来进行排序。实现堆排序的思路是,把数组构建成一棵二叉树,并随着每次堆的变化更新堆顶的最大/最小值。堆排序的时间复杂度在所有情况下都是 O(nlgn),它也是一个不稳定的算法。在开始编写堆排序的程序之前,我们首先要了解“堆”的概念。

是一种数据结构,它是一种特殊的完全二叉树:如果这个堆是一个大顶堆(最大的元素在堆顶),那么每个节点上的元素都应该比它的子节点上的元素要大,最大的元素在根节点上;反之,如果是小顶堆,那么每个节点上的元素都应该比它的子节点小,最小的元素在根节点上。

图 1 所示为大顶堆,位于根节点上的 59 是整个堆中最大的数。在堆排序中,我们需要把堆用一个数组的形式表示。
大顶堆
图 1:大顶堆

如图 2 所示,为堆的每一个节点编号。从根节点开始,把完全二叉树的每一层从左到右依次编号。图 2 就是前面的堆编好号的结果。随后,以编号为下标,把堆里的每一个元素放到一个数组里。
节点编号
图 2:节点编号

图 3 就是堆里的元素存放在数组中的样子。
二叉树的数组表示方式
图 3:二叉树的数组表示方式

因为数组的下标从 0 开始,而堆的编号从 1 开始,所以数组的第一个位置留空。为什么可以这样存放元素呢?观察堆的编号,我们发现每个非叶子节点的左子节点,其编号都为父节点的两倍;每个非叶子节点的右子节点,其编号都为父节点的两倍加一。

所以,在数组中,我们可以对元素的下标进行相似的操作,从而找到每个节点的子节点。比如,当父亲节点的下标为 n 时,左子节点的下标为 2n,右子节点的下标为 2n+1。

由于大顶堆和小顶堆的性质(最大/最小的元素在根节点),我们可以通过它们对数组进行排序。我们以使用大顶堆升序排序为例。我们先把待排序序列构造成一个初始大顶堆。

编写一个函数,只用于实现一个功能:给定一个堆,当除其根节点之外所有节点都符合堆性质时,对其根节点向下进行调整,直到堆中的所有元素都符合堆性质。

具体步骤如下:从根节点开始,把父亲节点的值和两个子节点中较大的那个进行比较,如果父亲节点较小,就把它和较大的子节点互换位置,并再次对这个子节点作为根节点的堆调用这个方法进行调整。否则,父亲节点的值大于两个子节点,证明堆中的所有数已经符合堆性质,所以结束整个方法。

1) 以图 4 中的堆为例,除堆顶 3 外,堆的其他元素都符合堆性质。
堆排序
图 4:堆排序

2) 为了维护堆性质,应从 3 的两个子节点中选出较大的那一个与 3 作比较。如图 5 所示,3 比 17 要小,所以 17 应该与 3 交换位置。
交换元素位置
图 5:交换元素位置

3) 交换完成后,3 成了 17 的左子节点。类似地,如图 6 所示,再把 3 与它两个子节点中较大的比较。4 比 3 大,所以 3 再次与 4 交换位置。
交换元素位置
图 6:交换元素位置

4) 如图 7 所示,最后一次调整结束后,3 已经是堆的叶子节点,不再有与它相连的子节点。这时候,调整就完成了。
完成调整
图 7:完成调整

若要初始化一个大顶堆,我们使用上述函数,对给定堆中所有的非叶子节点进行遍历调整。把堆末尾的节点的编号除以 2,便可得到堆中所有非叶子节点中,位于最深层最右侧的非叶子节点的编号。从后往前,遍历所有编号小于等于这个编号的节点。

1) 如图 8 所示,在我们构造的堆中,从数值为 1 的节点开始,一直遍历到数值为 59 的根节点。每遍历一个节点,都对它使用将堆顶向下调整的函数。此时节点所处于的堆,由它自身及它的两个子树组成。
初始化
图 8:初始化

为什么要从非叶子节点的最底层开始调整?如图 8 中圈出来的部分一样,此时节点的两个子树都是叶子节点。因为它们只有单个节点,所以它们必定符合堆性质,因此我们可以直接对最底层的非叶子节点使用之前讲到的函数。

当所有最底层的非叶子节点都调整完毕后,遍历到高一层的非叶子节点。这时候,它们的子树已经被调整完毕,符合堆性质,所以也可以使用调整函数。依此类推,可以证明算法的正确性。

2) 初始化大顶堆完成后,就可以进行堆排序了,如图 9 所示。
大顶堆初始化完成
图 9:大顶堆初始化完成

3) 初始化完成后,我们知道堆顶的值一定是整个堆中最大的。这时候,我们把它与堆末尾的元素交换,并把这个最大值从堆中删除,如图 10 所示。此时,堆的大小减小 1。
把最大值放到末尾并从堆中删除
图 10:把最大值放到末尾并从堆中删除

4) 接下来,由于整个堆中除了堆顶都符合堆性质,我们对堆顶使用向下调整的函数,如图 11 所示。调整完毕后,整个堆中的最大值,也就是整个数组中的次大值,就出现在了堆顶。
把第二大元素调整到堆顶
图 11:把第二大元素调整到堆顶

5) 类似地,把堆顶和堆末尾元素交换,再对堆顶进行向下调整,如图 12 所示。此时,数组中的次大值位于数组的倒数第二个位置。
重复相似步骤
图 12:重复相似步骤

6) 对堆中的元素重复这两个步骤,直到堆的大小只剩 1 个元素,也就是根节点为止。到那时,根节点上的元素必是数组中的最小值,如图 13 所示。
 堆排序完成
图 13:堆排序完成

我们可以看出,堆排序完成后,按照数组编号顺序的元素是升序排列的。

堆排序代码:
nums = [4,2,61,8,953,1,3,72,310,113,93,112,32,43,15,5,20,999,678,34,3,2]
def Heapify(start,end): #向下调整的函数,传入数据为堆顶节点的编号和堆末尾的界限值
    father = start
    son = father * 2    #son存储较大的子节点的编号,初始化为左子节点
    while son <= end:   #当目前数据所处的节点还有子节点时,继续循环调整
        if son+1 <= end and nums[son+1] > nums[son]:
            #如果存在右节点且其值大于左子节点的值,son存储右子节点的编号
            son += 1
        if nums[father] < nums[son]:     #如果父亲节点的值小于子节点
            nums[father],nums[son] = nums[son],nums[father] #交换父亲和子节点
            father = son
            son = father * 2         #进入下一层继续调整
        else:                #如果父亲节点大于等于子节点,调整完成
            return
def HeapInit():              #初始化大顶堆的函数
    nums.insert(0,0)
    #堆顶编号从开始,在位置0插入一个数使得堆中元素的编号与在数组中的下标一样
    for i in range((len(nums)-1)//2,0,-1):  #从最底层最右侧的非叶子节点开始调整
        Heapify(i,len(nums)-1)
def HeapSort():              #堆排序函数
    for i in range(len(nums)-1,0,-1):    #从堆末尾开始进行元素交换
        nums[1],nums[i] = nums[i],nums[1]
        Heapify(1,i-1)
HeapInit()
HeapSort()
print(nums)
程序的运行结果为:

[0, 1, 2, 2, 3, 3, 4, 5, 8, 15, 20, 32, 34, 43, 61, 72, 93, 112, 113, 310, 678, 953, 999]


先调用 HeapInit( ) 函数对堆进行初始化。函数中的 for 循环对所有非叶子节点进行遍历。传进向下调整的 Heapify( ) 函数的参数有两个,一个是要调整的堆的堆顶,另一个是堆中最大的叶子节点的范围。因为可能调整的所有堆的末尾都是叶子节点,而叶子节点的编号乘 2 必定大于数组长度,所以可以使用要排序的数组长度(len(nums)-1,因为下标 0 的元素不在排序范围内)作为范围。

初始化大顶堆完成后,再调用堆排序函数进行排序。需要注意的是,堆中的最大值与堆末尾元素交换后,它就从堆中被删去了,所以在调用 Heapify( ) 函数时,堆的范围是原本堆末尾元素的编号减 1,即 i-1。

否则,如果没有把堆末尾减 1,堆中的最大值在堆的末尾,那么除堆顶元素外的两个子树之一不符合堆性质,也就不符合向下调整的条件。for 循环结束后,堆排序就完成了。如果想要降序排序,把大顶堆转换成小顶堆即可。