整理定义

复述展开

前置概念

在理解堆排序之前，需要了解下什么是堆？

堆：堆(Heap)是计算机科学中一类特殊的数据结构，是最高效的优先级队列。堆通常是一个可以被看作一棵完全二叉树的数组对象。——百度百科

另外，还有两个概念需要了解：

大顶堆（最大堆，大根堆）：指的是最大元素在根节点（root）的堆，它的根节点始终大于它的子节点

小顶堆（最小堆，小根对）：指的是最小元素在根节点（root）的堆，它的根节点始终小于它的子节点

  iLeftChild(i)  = 2⋅i + 1
  iRightChild(i) = 2⋅i + 2
  iParent(i)     = floor((i−1) / 2)

堆排序就是利用堆的这一特性进行数据的排序。

算法原理

算法步骤
1.将初始待排序列 (R1, R2, ……, Rn) 构建成大顶堆，此堆为初始的无序区；
2.将堆顶元素 R[1] 与最后一个元素 R[n] 交换，此时得到新的无序区 (R1, R2, ……, Rn-1) 和新的有序区 (Rn), 且满足 R[1, 2, ……, n-1]<=R[n]；
3.由于交换后新的堆顶 R[1] 可能违反堆的性质，因此需要对当前无序区 (R1, R2, ……, Rn-1) 调整为新堆，然后再次将 R [1] 与无序区最后一个元素交换，
得到新的无序区 (R1, R2, ……, Rn-2) 和新的有序区 (Rn-1, Rn)。不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成。

建堆，将数据转化为一维数组表示的初始化堆（大顶堆），长度为N
将根节点（最大值）与节点 N 交换值，然后调整堆，使之满足大顶堆。
N = N-1
重复2-3步骤，直至N=0，此时所有节点都排好序。

代码实现

def swap(nums, i, j):
    nums[i], nums[j] = nums[j], nums[i]


class HeapSort:

    def __init__(self, nums):
        # 初始化全局变量，堆剩下还需要排序的长度
        self.heap_len = len(nums)

    def heapify(self, nums, i):
        """
        调整以 i 为根节点的堆，使之成为大根堆
        这里使用递归的方式
        """
        largest = i
        left = i * 2 + 1
        right = i * 2 + 2
        if left < self.heap_len and nums[largest] < nums[left]:
            largest = left
        if right < self.heap_len and nums[largest] < nums[right]:
            largest = right
        if largest != i:
            # 交换
            swap(nums, largest, i)
            self.heapify(nums, largest)

    def build_heap(self, nums):
        for i in range(self.heap_len // 2 - 1, -1, -1):
            self.heapify(nums, i)

    def heap_sort(self, nums):
        self.build_heap(nums)
        while self.heap_len > 0:
            # 交换
            swap(nums, self.heap_len - 1, 0)
            self.heap_len -= 1
            self.heapify(nums, 0)
        return nums


if __name__ == '__main__':
    nums = [3, 4, 1, 2, 7, 9, 3, 4, 1]
    solution = HeapSort(nums)
    print(solution.heap_sort(nums))