Skip to content

Latest commit

 

History

History
111 lines (84 loc) · 6.04 KB

07.Array-Heap-Sort.md

File metadata and controls

111 lines (84 loc) · 6.04 KB

1. 堆排序算法思想

堆排序（Heap sort）基本思想：

借用「堆结构」所设计的排序算法。将数组转化为大顶堆，重复从大顶堆中取出数值最大的节点，并让剩余的堆维持大顶堆性质。

1.1 堆的定义

堆：符合以下两个条件之一的完全二叉树：

  • 大顶堆：根节点值 ≥ 子节点值。
  • 小顶堆：根节点值 ≤ 子节点值。

2. 堆排序算法步骤

  • 首先将无序序列构造成第 1 个大顶堆（初始堆），使得 n 个元素的最大值处于序列的第 1 个位置。
  • 然后交换序列的第 1 个元素（最大值元素）与最后一个元素的位置。
  • 此后，再把序列的前 n - 1 个元素组成的子序列调整成一个新的大顶堆，这样又得到第 2 个最大值元素，把子序列的第 1 个元素（最大值元素）与第 n - 1 个元素交换位置。
  • 此后再把序列的前 n - 2 个元素调整成一个新的大顶堆，……，如此下去，直到整个序列变换成一个有序序列。

可见堆排序算法主要涉及「初始堆建立方法」和「堆调整方法」。

2.1 堆调整方法

堆调整方法就是：把移走了最大值元素以后的剩余元素组成的序列再构造为一个新的堆积。具体步骤如下：

  • 从根节点开始，自上而下地调整节点的位置，使其成为堆积。即把序号为 i 的节点与其左子树节点（序号为 2 * i）、右子树节点（序号为 2 * i + 1）中值最大的节点交换位置。
  • 因为交换了位置，使得当前节点的左右子树原有的堆积特性被破坏。于是，从当前节点的左右子树节点开始，自上而下继续进行类似的调整。
  • 如此下去直到整棵完全二叉树成为一个大顶堆。

2.2 初始堆建立方法

  • 如果原始序列对应的完全二叉树（不一定是堆）的深度为 d，则从 d - 1 层最右侧分支节点（序号为 $\lfloor n/2 \rfloor$）开始，初始时令 $i = \lfloor n/2 \rfloor$，调用堆调整算法。
  • 每调用一次堆调整算法，执行一次 i = i - 1，直到 i == 1 时，再调用一次，就把原始序列调整为了一个初始堆。

3. 堆排序动画演示

3.1 堆调整方法演示

3.2 初始堆建立方法演示

3.3 堆排序方法演示

4. 堆排序算法分析

  • 堆积排序的时间主要花费在两个方面：
    • 将原始序列构造为一个初始堆积。
    • 排序过程中不断将移走最大值元素，然后将剩下元素重新调整为一个新堆积。
  • 设原始序列所对应的完全二叉树深度为 d，算法由两个独立的循环组成：
    • 在第 1 个循环构造初始堆积时，从 i = d - 1 层开始，到 i = 1 层为止，对每个分支节点都要调用一次 adjust 算法，每一次 adjust 算法，对于第 i 层一个节点到第 d 层上建立的子堆积，所有节点可能移动的最大距离为该子堆积根节点移动到最后一层（第 d 层） 的距离即 d - i。
    • 而第 i 层上节点最多有 $2^{i-1}$ 个，所以每一次 adjust 算法最大移动距离为 $2^{i-1} * (d-i)$。因此，堆积排序算法的第 1 个循环所需时间应该是各层上的节点数与该层上节点可移动的最大距离之积的总和，即：$\sum_{i = d - 1}^1 2^{i-1} (d-i) = \sum_{j = 1}^{d-1} 2^{d-j-1} \times j = \sum_{j = 1}^{d-1} 2^{d-1} \times {j \over 2^j} \le n \sum_{j = 1}^{d-1} {j \over 2^j} < 2n$。这一部分时间花费为 $O(n)$。
    • 在算法的第 2 个循环中每次调用 adjust 算法一次，节点移动的最大距离为这棵完全二叉树的深度 $d = \lfloor log_2(n) \rfloor + 1$，一共调用了 n - 1 次 adjust 算法，所以，第 2 个循环的时间花费为 $(n-1)(\lfloor log_2 (n)\rfloor + 1) = O(n log_2 n)$。
  • 因此，堆积排序的时间复杂度为 $O(nlog_2 n)$。
  • 由于在堆积排序中只需要一个记录大小的辅助空间，因此，堆积排序的空间复杂度为：$O(1)$。
  • 堆排序属于 不稳定排序算法。堆排序也是一种不适合在链表上实现的排序。

5. 堆排序代码实现

class Solution:
    # 调整为大顶堆
    def heapify(self, arr: [int], index: int, end: int):
        left = index * 2 + 1
        right = left + 1
        while left <= end:
            # 当前节点为非叶子结点
            max_index = index
            if arr[left] > arr[max_index]:
                max_index = left
            if right <= end and arr[right] > arr[max_index]:
                max_index = right
            if index == max_index:
                # 如果不用交换，则说明已经交换结束
                break
            arr[index], arr[max_index] = arr[max_index], arr[index]
            # 继续调整子树
            index = max_index
            left = index * 2 + 1
            right = left + 1

    # 初始化大顶堆
    def buildMaxHeap(self, arr: [int]):
        size = len(arr)
        # (size-2) // 2 是最后一个非叶节点，叶节点不用调整
        for i in range((size - 2) // 2, -1, -1):
            self.heapify(arr, i, size - 1)
        return arr

    # 升序堆排序，思路如下：
    # 1. 先建立大顶堆
    # 2. 让堆顶最大元素与最后一个交换，然后调整第一个元素到倒数第二个元素，这一步获取最大值
    # 3. 再交换堆顶元素与倒数第二个元素，然后调整第一个元素到倒数第三个元素，这一步获取第二大值
    # 4. 以此类推，直到最后一个元素交换之后完毕。
    def maxHeapSort(self, arr: [int]):
        self.buildMaxHeap(arr)
        size = len(arr)
        for i in range(size):
            arr[0], arr[size - i - 1] = arr[size - i - 1], arr[0]
            self.heapify(arr, 0, size - i - 2)
        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.maxHeapSort(nums)