堆排序

1. 简介

https://blog.csdn.net/qq_28063811/article/details/93034625/

https://blog.csdn.net/weixin_50941083/article/details/121096435

堆是一种完全二叉树的数据结构。由于完全二叉树的性质，对于每个节点，都能推算出其父节点和左右子节点的索引。因此堆可以用数组来表示。

大顶堆：每个节点的值都大于或者等于它的左右子节点的值。

小顶堆：每个节点的值都小于或者等于它的左右子节点的值。

2. 特点

1. 对于一个完全二叉树上的节点i，其左右子节点index为2*i+1和2*i+2,父节点index为(i-1)//2

   1. 假设i所在层为n（该层元素个数为$ 2 ^ {n} $,等于其所有上层元素个数和➕1），i所在层前方有k个元素。则有 $i = 2^{n} - 1 + k$
   2. 对于其左子节点j, 有 $ j = 2^{n+1} - 1 + 2*k$。所以 $ j = 2 * i + 1 $，右子节点为 $ 2 * i + 2$
   3. 同理算出父节点index
   4. 最后一个父节点为尾节点的父节点，即为$ (len - 1 - 1) // 2 = len // 2 - 1$

2. 大顶堆堆顶的元素是最大的元素，小顶堆堆顶的元素是最小的元素

3. 堆排序的基本思想是：

   1. 将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；
   2. 将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；
   3. 重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。

4. 复杂度分析：

   1. 交换及重建大顶堆的过程中，需要交换n-1次，重建大顶堆的过程根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为O(nlog(n))
   2. heap_insert初始化大顶堆时间复杂度为O(nlog(n))。 heapify则为O(n)

3. 实现

1. heap_insert初始化

from typing import List


def heap_sort(arr: List):
    # 第一步: 使用heap_insert将初始的数组构建为大顶堆
    for index in range(1, len(arr)):
        heap_insert(arr, index)

    # 第二步: 逐个将堆顶与堆尾交换, 堆尾-1, 并将其重新调整为大顶堆
    heapsize = len(arr) - 1
    while heapsize > 0:
        arr[0], arr[heapsize] = arr[heapsize], arr[0] # 交换最大节点和最后一个子节点
        heapsize -= 1
        heapify(arr, heapsize)


def heap_insert(arr: List, index: int):
    """调整索引为index处, 使得arr[0:index+1]为大顶堆
    适用于初始阶段, 调整整个arr成为大顶堆.
    """
    # 如果新加入的节点值大于其父节点, 则交换。其他分支不受影响
    parent_index = (index-1) // 2
    while parent_index >= 0 and arr[index] > arr[parent_index]:
        arr[index], arr[parent_index] = arr[parent_index], arr[index]
        index = parent_index
        parent_index = (index-1) // 2


def heapify(arr: List, index: int):
    """对于一个大顶堆, 堆顶和index+1值交换后, 重新调整, 使得arr[0:index+1]为大顶堆。
    复杂度为log(n)
    """
    i = 0
    while 2*i+1 <= index:
        if 2*i+2 <= index:  # 左右节点均存在
            swap_index = 2*i+2 if arr[2*i+2] > arr[2*i+1] else 2*i+1
        else:
            swap_index = 2*i+1
        if arr[i] < arr[swap_index]:
            arr[i], arr[swap_index] = arr[swap_index], arr[i]
            i = swap_index
        else:
            break

2. heapify初始化

from typing import List


def heap_sort(arr: List):
    # 第一步: 使用build_max_heap将初始的数组构建为大顶堆
    build_max_heap(arr)

    # 第二步: 逐个将堆顶与堆尾交换, 堆尾-1, 并将其重新调整为大顶堆
    heapsize = len(arr) - 1
    while heapsize > 0:
        arr[0], arr[heapsize] = arr[heapsize], arr[0] # 交换最大节点和最后一个子节点
        heapsize -= 1
        heapify(arr, 0, heapsize)


def build_max_heap(arr: List):
    """从第一个非叶子节点开始，从右至左，从下至上调整子树为大根堆，最终整个堆为大根堆
    """
    i = len(arr) // 2 - 1 #第一个非叶子节点
    while i >= 0:
        heapify(arr, i, len(arr)-1)
        i -= 1


def heapify(arr: List, start: int, index: int):
    """重新调整, 使得arr[start:index+1]为大顶堆
    """
    i = start
    while 2*i+1 <= index:
        if 2*i+2 <= index:  # 左右节点均存在
            swap_index = 2*i+2 if arr[2*i+2] > arr[2*i+1] else 2*i+1
        else:
            swap_index = 2*i+1
        if arr[i] < arr[swap_index]:
            arr[i], arr[swap_index] = arr[swap_index], arr[i]
            i = swap_index
        else:
            break

4. 解题

https://leetcode.cn/problems/kth-largest-element-in-an-array/

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

def build_max_heap(arr):
    """从第一个非叶子节点开始，从右至左，从下至上调整子树为大根堆，最终整个堆为大根堆
    """
    i = len(arr) // 2 - 1
    while i >= 0:
        heapify(arr, i, len(arr)-1)
        i -= 1


def heapify(arr, start, index):
    """重新调整, 使得arr[start:index+1]为大顶堆
    """
    i = start
    while 2*i+1 <= index:
        if 2*i+2 <= index:  # 左右节点均存在
            swap_index = 2*i+2 if arr[2*i+2] > arr[2*i+1] else 2*i+1
        else:
            swap_index = 2*i+1
        if arr[i] < arr[swap_index]:
            arr[i], arr[swap_index] = arr[swap_index], arr[i]
            i = swap_index
        else:
            break

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        # 第一步: 使用build_max_heap将初始的数组构建为大顶堆
        build_max_heap(nums)

        # 第二步: 逐个将堆顶与堆尾交换, 堆尾-1, 并将其重新调整为大顶堆
        heapsize = len(nums) - 1
        idx = k
        while heapsize > len(nums) - k - 1:
            nums[0], nums[heapsize] = nums[heapsize], nums[0] # 交换最大节点和最后一个子节点
            heapsize -= 1
            heapify(nums, 0, heapsize)
        return nums[-k]