排序算法（7）：堆排序

问题

排序 [30, 24, 5, 58, 18, 36, 12, 42, 39]

堆排序

堆排序是一种基于堆数据结构的排序算法。堆是一个近似完全二叉树的结构，即除了最后一层外，每一层都必须填满，且最后一层从左往右填充。

堆可以分为大根堆和小根堆。在大根堆中，父节点的值总是大于或等于其子节点的值，因此根节点存储的是最大值。在小根堆中，父节点的值总是小于或等于其子节点的值，因此根节点存储的是最小值。二叉堆中两个子节点的大小没有关系。
在这里插入图片描述

图解

堆排序通常使用大根堆来进行升序排序。

构建大根堆：每次将新插入元素的值与父节点值进行比较，如果新插入的数比父节点大，则与父节点进行交换，一直向上交换直到小于父节点的值或者到达顶端。

如上图所示，在插入 58 时，先与父节点 24 进行比较，发现大于父节点的值，与父节点交换位置；再次与父节点 30 进行比较后交换，直到位于根节点。

最终生成的大根堆如下图所示：

由图可以看出，一直当前节点为 i，则父节点为 (i - 1) // 2，左子节点为 i * 2 + 1，右子节点为 i * 2 + 2
固定最大值再重构大根堆：将堆顶的最大值与末位元素进行交换，然后将剩余的数再构建成一个大根堆。

交换堆顶元素和末位元素，此时最大值 58 来到最后一位固定住，不再参与接下来的排序。

接下来要调整堆顶的元素使剩余的数再次构建一个大根堆：首先将堆顶的数与其左右子节点的最大值进行比较，如果堆顶的数更大，停止；如果堆顶的数小于左右子节点的最大值，则进行位置交换，逐级向下交换直到大于子节点的值或交换到最底层。
重复执行第二步最终得到有序数组

代码

# 构建大根堆（通过新插入的数上升）
def heap_insert(nums):
	for i in range(1, len(nums)):
        current = i
        parent = (current - 1) // 2

        while parent >= 0 and nums[current] > nums[parent]:
            nums[current], nums[parent] = nums[parent], nums[current]
            current = parent
            parent = (current - 1) // 2

    return nums

# 再构大根堆（通过堆顶的数下沉）
def heapify(arr, i, n):
	largest = i
	left = 2 * i + 1
	right = 2 * i + 2

	if left < n and arr[left] > arr[right]:
        largest = left
    if right < n and arr[right] > arr[left]:
        largest = right

    if largest != i:
        arr[largest], arr[i] = arr[i], arr[largest]
        heapify(arr, largest, n)

# 堆排序
def heap_sort(nums):
	nums = heap_insert(nums)
    n = len(nums)

    while n > 1:
        nums[0], nums[n-1] = nums[n-1], nums[0]
        n -= 1
        nums = heapify(nums, 0, n)

    return nums