堆排序算法总结

一、堆排序算法

1. 算法步骤

堆的基本概念

堆（Heap）是一种特殊的完全二叉树数据结构，它满足以下性质：

• 完全二叉树：除了最后一层外，其他层的节点数都是最大的，最后一层的节点都靠左排列
• 堆序性质：每个节点的值都大于等于（或小于等于）其子节点的值

根据堆序性质的不同，堆可以分为两种类型：

• 最大堆（Max Heap）：每个节点的值都大于等于其子节点的值
• 最小堆（Min Heap）：每个节点的值都小于等于其子节点的值

堆的主要性质：

• 结构性质：堆是一个完全二叉树
• 堆序性质：父节点与子节点的大小关系始终满足特定条件
• 高度性质：n个节点的堆高度为⌊log₂n⌋

堆排序的基本步骤如下：

1. 构建最大堆（升序排序）或最小堆（降序排序）
2. 交换堆顶元素与堆的最后一个元素
3. 将堆的大小减1
4. 对新的堆顶元素执行下沉操作，恢复堆序性质
5. 重复步骤2-4，直到堆的大小为1

堆的核心操作

下沉操作（Sink/Down-Heap/Heapify）

下沉操作用于恢复被破坏的堆序性质，特别是在构建堆和排序过程中：

1. 找到当前节点和其子节点中的最大值
2. 如果最大值不是当前节点，交换它们
3. 继续对被交换的子节点执行下沉操作

构建堆方法

自底向上法（更高效）：

• 从最后一个非叶子节点开始，依次向前
• 对每个节点执行下沉操作
• 时间复杂度：O(n)

排序过程

将最大堆转换为排序数组：

• 交换堆顶元素（最大值）与最后一个元素
• 减小堆的大小
• 对新的堆顶执行下沉操作
• 重复直到堆为空

时间复杂度：O(n log n)
空间复杂度：O(1)，是一种原地排序算法
稳定性：不稳定排序

2. 图解过程

以数组[4, 10, 3, 5, 1]为例，演示堆排序过程（升序排序，使用最大堆）：

步骤1：构建最大堆

初始数组: [4, 10, 3, 5, 1]

从最后一个非叶子节点开始下沉:
i = (5/2)-1 = 1, arr[1] = 10
10已经大于其子节点，不需要下沉

i = 0, arr[0] = 4
4小于子节点10，交换4和10
[10, 4, 3, 5, 1]
继续下沉，4小于子节点5，交换4和5
[10, 5, 3, 4, 1]

最终构建的最大堆:
       10
     /    \
    5      3
   / \
  4   1

步骤2-5：排序过程

迭代1:
交换堆顶10和最后一个元素1
[1, 5, 3, 4, 10]
堆大小减1，新的堆为[1, 5, 3, 4]
下沉1，得到[5, 4, 3, 1]

迭代2:
交换堆顶5和最后一个元素1
[1, 4, 3, 5, 10]
堆大小减1，新的堆为[1, 4, 3]
下沉1，得到[4, 1, 3]

迭代3:
交换堆顶4和最后一个元素3
[3, 1, 4, 5, 10]
堆大小减1，新的堆为[3, 1]
下沉3，得到[3, 1]

迭代4:
交换堆顶3和最后一个元素1
[1, 3, 4, 5, 10]
堆大小减1，新的堆为[1]

最终排序结果: [1, 3, 4, 5, 10]

3. Java代码实现

public int[] sortArray(int[] nums) {
    int n = nums.length;
    
    // 构建最大堆（从最后一个非叶子节点n/2-1开始）
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(nums, n, i);
    }
    
    // 一个个从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        // 将当前堆顶（最大值）移到数组末尾
        swap(nums, 0, i);
        
        // 对剩余的堆进行heapify操作
        heapify(nums, i, 0);
    }
    
    return nums;
}

// 维护堆的性质
private void heapify(int[] nums, int n, int i) {
    int largest = i; // 假设当前节点是最大的
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点
    
    // 如果左子节点比当前节点大
    if (left < n && nums[left] > nums[largest]) {
        largest = left;
    }
    
    // 如果右子节点比当前最大节点还大
    if (right < n && nums[right] > nums[largest]) {
        largest = right;
    }
    
    // 如果最大值不是当前节点，交换并继续heapify
    if (largest != i) {
        swap(nums, i, largest);
        
        // 递归地维护受影响的子树
        heapify(nums, n, largest);
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

二、堆排序的应用场景

1. Top K问题

堆排序最常见的应用是解决Top K问题，即查找数组中第K大/小的元素或前K个最大/小的元素：

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    
    return minHeap.peek();
}

2. 优先队列实现

Java中的PriorityQueue就是基于堆实现的：

// 最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

优先队列广泛应用于：

• 任务调度
• 图算法（如Dijkstra最短路径算法）
• 事件模拟

3. 中位数和百分位数计算

使用两个堆（一个最大堆和一个最小堆）可以高效地计算数据流的中位数：

class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // 存储较小的一半元素
    private PriorityQueue<Integer> minHeap; // 存储较大的一半元素
    
    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());
        
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        } else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
}

4. 定时器实现

使用最小堆可以高效地实现定时器，堆顶总是最早需要触发的事件：

class Timer {
    private PriorityQueue<Event> eventQueue;
    
    public Timer() {
        eventQueue = new PriorityQueue<>((a, b) -> 
            Long.compare(a.executionTime, b.executionTime));
    }
    
    public void schedule(Runnable task, long delay) {
        long executionTime = System.currentTimeMillis() + delay;
        eventQueue.offer(new Event(task, executionTime));
    }
    
    public void run() {
        while (!eventQueue.isEmpty()) {
            Event event = eventQueue.peek();
            long currentTime = System.currentTimeMillis();
            
            if (currentTime >= event.executionTime) {
                eventQueue.poll();
                event.task.run();
            }
        }
    }
    
    private static class Event {
        Runnable task;
        long executionTime;
        
        Event(Runnable task, long executionTime) {
            this.task = task;
            this.executionTime = executionTime;
        }
    }
}

5. 排序算法比较

堆排序的优势：

• 最坏情况下仍然保持O(n log n)的时间复杂度
• 空间复杂度为O(1)，是原地排序算法
• 不受输入数据分布的影响

堆排序的劣势：

• 实际运行时间通常比快速排序慢
• 不稳定排序
• 对缓存不友好，因为堆结构导致的内存访问模式不连续