堆排序

基本概念

堆排序（Heap sort）基本思想：
利用堆的特性，将数组构建成大顶堆，然后重复取出堆顶元素（最大值）并调整堆结构，最终得到有序数组。

算法步骤

堆排序分为两个主要阶段：

第一阶段：构建初始大顶堆

  1. 将原始数组视为完全二叉树

  2. 从最后一个非叶子节点开始，自底向上进行下移调整

  3. 将数组转换为大顶堆
    第二阶段：重复提取最大值

  4. 交换堆顶元素与当前末尾元素

  5. 堆长度减 1，末尾元素已排好序

  6. 对新的堆顶元素进行下移调整，恢复堆的性质

  7. 重复步骤 1∼3，直到堆的大小为 1

内部实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class MaxHeap:
    def __init__(self):
        self.max_heap = []
    
    def __buildMaxHeap(self, nums: [int]):
        # 将数组元素复制到堆中
        self.max_heap = nums.copy()
        size = len(nums)
        
        # 从最后一个非叶子节点开始，自底向上构建堆
        for i in range((size - 2) // 2, -1, -1):
            self.__shift_down(i, size)

    def maxHeapSort(self, nums: [int]) -> [int]:
        # 第一阶段：构建初始大顶堆
        self.__buildMaxHeap(nums)
        
        size = len(self.max_heap)
        # 第二阶段：重复提取最大值
        for i in range(size - 1, -1, -1):
            # 交换堆顶元素与当前末尾元素
            self.max_heap[0], self.max_heap[i] = self.max_heap[i], self.max_heap[0]
            # 对新的堆顶元素进行下移调整，堆的大小为 i
            self.__shift_down(0, i)
        
        # 返回排序后的数组
        return self.max_heap
    
    def __shift_down(self, i: int, n: int):
        # 下移调整：将节点与其较大的子节点比较并交换
        while 2 * i + 1 < n:
            left, right = 2 * i + 1, 2 * i + 2
            
            # 找出较大的子节点
            larger = left
            if right < n and self.max_heap[right] > self.max_heap[left]:
                larger = right
            
            # 如果当前节点小于较大子节点，则交换
            if self.max_heap[i] < self.max_heap[larger]:
                self.max_heap[i], self.max_heap[larger] = self.max_heap[larger], self.max_heap[i]
                i = larger
            else:
                break

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

复杂度分析：

指标 复杂度 说明
最佳时间复杂度 O(nlog⁡n)O(nlog⁡n) 无论数组状态如何，都需要构建堆和提取元素
最坏时间复杂度 O(nlog⁡n)O(nlog⁡n) 无论数组状态如何，都需要构建堆和提取元素
平均时间复杂度 O(nlog⁡n)O(nlog⁡n) 堆排序的时间复杂度与数据状态无关
空间复杂度 O(1)O(1) 原地排序，只使用常数空间
稳定性 不稳定 调整堆的过程中可能改变相等元素的相对顺序
适用场景：
  • 大规模数据排序
  • 内存受限的环境
  • 需要稳定时间复杂度的场景
  • 需要保证最坏情况下性能的场景
    堆排序是一种基于堆数据结构的排序算法，利用堆的特性实现高效排序。
    核心思想：
  • 将数组构建成大顶堆，堆顶元素始终是最大值
  • 重复取出堆顶元素并调整堆结构，最终得到有序数组
    算法步骤：
  1. 构建初始堆：将数组转换为大顶堆
  2. 重复提取：交换堆顶与末尾元素，调整堆结构，逐步得到有序数组
  • 优点：
    • 时间复杂度稳定，始终为 O(nlog⁡n)
    • 空间复杂度低，为 O(1)
    • 适合处理大规模数据
    • 原地排序，不需要额外空间
  • 缺点：
    • 不稳定排序
    • 常数因子较大，实际应用中可能比快速排序稍慢
    • 对缓存不友好，访问模式不够局部化

堆排序是一种同时具备 O(nlog⁡n)时间复杂度和 O(1) 空间复杂度的比较排序算法，在内存受限或需要稳定时间复杂度的场景下具有重要价值

应用场景：