堆与优先队列为什么能在对数时间内找到第K大元素:从完全二叉树到堆排序的完整技术解析

1964年，J.W.J. Williams在发表堆排序算法时，顺带发明了一种被称为"堆"的数据结构。他可能没想到，这个最初为排序服务的数据结构，会在六十年后成为每一位程序员面试的必考内容。从操作系统进程调度到网络路由的最短路径计算，从数据库查询优化到实时数据流的中位数统计，堆的身影无处不在。

堆的本质是一个满足特定约束的完全二叉树。大顶堆要求每个节点的值都不小于其子节点的值，小顶堆则相反。这个看似简单的约束，却催生了高效的优先队列实现——插入和删除操作都能在对数时间内完成。当问题涉及"前K个"、“第K大”、“实时维护最值"等关键词时，堆往往是首选方案。

完全二叉树的数组表示

堆的基础是完全二叉树，而完全二叉树的一个关键特性是可以用数组紧凑地表示。如果根节点存储在索引0，那么对于任意索引为i的节点：其左子节点在索引$2i+1$，右子节点在索引$2i+2$，父节点在索引$(i-1)/2$（向下取整）。

这种映射关系意味着不需要额外的指针来维护树结构，空间利用率达到100%。更重要的是，数组在内存中是连续存储的，这对缓存友好性有显著帮助。当然，相比快速排序的顺序访问模式，堆的跳访问模式在缓存效率上仍有劣势。

// 堆的索引计算
int parent(int i) { return (i - 1) >>> 1; }
int leftChild(int i) { return (i << 1) + 1; }
int rightChild(int i) { return (i << 1) + 2; }

堆的数组表示

图片来源: Wikipedia - Binary tree in array

上浮与下沉：堆的两种核心操作

堆的高效性来源于两个核心操作：上浮和下沉。这两个操作共同维护堆的性质，是所有堆操作的基础。

上浮操作（Sift Up）

当向堆中插入一个新元素时，将其放在数组末尾，然后与父节点比较。如果违反了堆性质（例如小顶堆中新元素小于父节点），则交换两者，继续向上比较，直到满足堆性质或到达根节点。上浮操作的路径是从叶子到根的一条路径，最坏情况下需要遍历树的高度，时间复杂度为$O(\log n)$。

// 小顶堆的上浮操作
private void siftUp(int[] heap, int index) {
    while (index > 0) {
        int parent = (index - 1) >>> 1;
        if (heap[index] >= heap[parent]) {
            break;  // 满足堆性质，停止
        }
        // 交换当前节点与父节点
        swap(heap, index, parent);
        index = parent;
    }
}

下沉操作（Sift Down）

当从堆顶取出元素后，将数组末尾的元素移到堆顶，然后与子节点比较。如果不满足堆性质，则与较大的子节点（大顶堆）或较小的子节点（小顶堆）交换，继续向下比较。下沉操作同样是对数时间。

// 小顶堆的下沉操作
private void siftDown(int[] heap, int index, int size) {
    int half = size >>> 1;  // 只需要检查非叶子节点
    while (index < half) {
        int child = (index << 1) + 1;  // 左子节点
        int right = child + 1;
        // 找到较小的子节点
        if (right < size && heap[right] < heap[child]) {
            child = right;
        }
        if (heap[index] <= heap[child]) {
            break;  // 满足堆性质，停止
        }
        swap(heap, index, child);
        index = child;
    }
}

下沉操作有一个微妙但重要的细节：必须先比较两个子节点，选择更合适的那一个进行交换。这保证了每次交换后堆性质尽可能得到满足，减少了后续调整的次数。

为什么下沉后还需要上浮？

Java的PriorityQueue在remove操作中有一个有趣的设计：先执行下沉，如果元素位置没变，再执行上浮。这是因为被移动的元素可能比它的子节点大（需要下沉），也可能比它的父节点小（需要上浮）。下沉操作只能处理前者，如果元素比所有子节点都小，下沉就不会移动它，但此时它可能需要上浮。

// Java PriorityQueue 的 removeAt 方法片段
private E removeAt(int i) {
    // ... 省略边界处理 ...
    E moved = (E) queue[s];
    queue[s] = null;
    siftDown(i, moved);
    if (queue[i] == moved) {
        siftUp(i, moved);
    }
    return moved;
}

建堆：O(n)的魔法

给定一个无序数组，如何将其转化为堆？直觉方法是逐个插入，每次插入需要$O(\log n)$，总共$O(n\log n)$。但1964年Floyd提出了一个更聪明的方法：从最后一个非叶子节点开始，依次对每个节点执行下沉操作。这个方法的时间复杂度是$O(n)$。

为什么是$O(n)$而不是$O(n\log n)$？关键在于不同高度的节点数量。设堆有$h$层（根为第0层），第$i$层有$2^i$个节点，每个节点的下沉深度最多为$h-i$。总操作次数为：

$$\sum_{i=0}^{h-1} 2^i \cdot (h-i)$$

通过数学变换可得总和约为$2^{h+1} - h - 2$，而$n \approx 2^h$，所以总时间复杂度为$O(n)$。

// 建堆操作
public void buildHeap(int[] arr) {
    int n = arr.length;
    // 从最后一个非叶子节点开始，依次下沉
    for (int i = (n >>> 1) - 1; i >= 0; i--) {
        siftDown(arr, i, n);
    }
}

直观理解：底层节点数量多但下沉深度小，顶层节点数量少但下沉深度大。这种"数量与深度的互补"使得总工作量是线性的。

Java中的PriorityQueue

Java的PriorityQueue是基于小顶堆实现的优先队列。默认情况下，元素按自然顺序排列（最小的在堆顶），也可以通过传入Comparator来定制排序规则。

// 默认小顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
// 或使用 Comparator.reverseOrder()
PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>(Comparator.reverseOrder());

// 常用操作
minHeap.offer(5);      // 插入元素，O(log n)
minHeap.poll();        // 取出堆顶元素，O(log n)
minHeap.peek();        // 查看堆顶元素，O(1)
minHeap.size();        // 堆的大小

PriorityQueue的一个重要限制是不支持高效删除任意元素。虽然提供了remove(Object o)方法，但需要$O(n)$时间定位元素。如果需要频繁删除任意元素，应该考虑使用TreeSet或自定义数据结构。

自定义对象的优先队列

当存储自定义对象时，需要提供比较逻辑：

// 方法1：让类实现 Comparable 接口
class Task implements Comparable<Task> {
    int priority;
    String name;
    
    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }
}

// 方法2：传入 Comparator
PriorityQueue<Task> pq = new PriorityQueue<>(
    (a, b) -> Integer.compare(a.priority, b.priority)
);

// 方法3：静态 Comparator（适用于复杂比较逻辑）
PriorityQueue<Task> pq = new PriorityQueue<>(
    Comparator.comparingInt(Task::getPriority)
              .thenComparing(Task::getName)
);

堆排序：被低估的排序算法

堆排序是堆数据结构的直接应用。过程分为两步：首先将数组建成大顶堆，然后反复取出堆顶（最大值）放到数组末尾，对剩余部分重新调整堆。

public void heapSort(int[] arr) {
    int n = arr.length;
    
    // 第一步：建堆（大顶堆）
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // 第二步：排序
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);      // 将堆顶放到末尾
        heapify(arr, i, 0);   // 对剩余部分重新调整
    }
}

private void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, n, largest);
    }
}

堆排序的时间复杂度稳定为$O(n\log n)$，空间复杂度$O(1)$，且没有最坏情况。那为什么实际中快速排序更常用？

核心原因在于缓存效率和常数因子。快速排序的顺序访问模式与现代CPU缓存极其契合，而堆排序的随机访问模式导致大量缓存缺失。实测显示，快速排序通常比堆排序快2-3倍。但堆排序的优势在于稳定的最坏情况性能和原地排序，这在某些场景下非常重要。

LeetCode题型全解析

题型一：TopK问题

TopK问题是最经典的堆应用场景。核心思想是：维护一个大小为K的堆，遍历数组时保持堆中始终是当前的前K个元素。

LeetCode 215. 数组中的第K个最大元素

public int findKthLargest(int[] nums, int k) {
    // 使用小顶堆，堆顶是第K大的元素
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    
    for (int num : nums) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();  // 移除最小的，保留较大的K个
        }
    }
    
    return heap.peek();
}

时间复杂度$O(n\log k)$，空间复杂度$O(k)$。当$k$远小于$n$时，这比排序整个数组的$O(n\log n)$高效得多。

这道题还有另一种经典解法——快速选择算法，平均时间复杂度$O(n)$，但最坏情况$O(n^2)$。堆方法的稳定性在某些场景下更有价值。

LeetCode 347. 前K个高频元素

public int[] topKFrequent(int[] nums, int k) {
    // 统计频率
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int num : nums) {
        freqMap.merge(num, 1, Integer::sum);
    }
    
    // 小顶堆，按频率排序
    PriorityQueue<Integer> heap = new PriorityQueue<>(
        (a, b) -> freqMap.get(a) - freqMap.get(b)
    );
    
    for (int num : freqMap.keySet()) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        result[i] = heap.poll();
    }
    return result;
}

LeetCode 973. 最接近原点的K个点

public int[][] kClosest(int[][] points, int k) {
    // 大顶堆，保留距离最小的K个点
    PriorityQueue<int[]> heap = new PriorityQueue<>(
        (a, b) -> distance(b) - distance(a)
    );
    
    for (int[] point : points) {
        heap.offer(point);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    
    int[][] result = new int[k][2];
    for (int i = 0; i < k; i++) {
        result[i] = heap.poll();
    }
    return result;
}

private int distance(int[] point) {
    return point[0] * point[0] + point[1] * point[1];
}

题型二：合并K个有序序列

LeetCode 23. 合并K个升序链表

这是一个经典的"多路归并"问题。使用小顶堆存储所有链表的当前节点，每次取出最小的节点加入结果链表。

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    
    // 小顶堆，按节点值排序
    PriorityQueue<ListNode> heap = new PriorityQueue<>(
        (a, b) -> a.val - b.val
    );
    
    // 将所有链表的头节点加入堆
    for (ListNode node : lists) {
        if (node != null) {
            heap.offer(node);
        }
    }
    
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (!heap.isEmpty()) {
        ListNode minNode = heap.poll();
        curr.next = minNode;
        curr = curr.next;
        
        if (minNode.next != null) {
            heap.offer(minNode.next);
        }
    }
    
    return dummy.next;
}

时间复杂度$O(n\log k)$，其中$n$是所有节点总数，$k$是链表数量。空间复杂度$O(k)$。

LeetCode 373. 查找和最小的K对数字

public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums1.length == 0 || nums2.length == 0) return result;
    
    // 小顶堆，存储索引对 (i, j)，按和排序
    PriorityQueue<int[]> heap = new PriorityQueue<>(
        (a, b) -> nums1[a[0]] + nums2[a[1]] - nums1[b[0]] - nums2[b[1]]
    );
    
    // 将nums1的每个元素与nums2[0]配对加入堆
    for (int i = 0; i < nums1.length && i < k; i++) {
        heap.offer(new int[]{i, 0});
    }
    
    while (k-- > 0 && !heap.isEmpty()) {
        int[] pair = heap.poll();
        result.add(Arrays.asList(nums1[pair[0]], nums2[pair[1]]));
        
        if (pair[1] + 1 < nums2.length) {
            heap.offer(new int[]{pair[0], pair[1] + 1});
        }
    }
    
    return result;
}

题型三：双堆技巧

LeetCode 295. 数据流的中位数

这道题展示了堆的一个经典技巧：使用两个堆来动态维护中位数。大顶堆存储较小的一半元素，小顶堆存储较大的一半元素，保持两个堆的大小差不超过1。

class MedianFinder {
    private PriorityQueue<Integer> maxHeap;  // 存储较小的一半
    private PriorityQueue<Integer> minHeap;  // 存储较大的一半
    
    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        // 先加入大顶堆
        maxHeap.offer(num);
        // 将大顶堆的最大值移到小顶堆
        minHeap.offer(maxHeap.poll());
        
        // 平衡：保证大顶堆元素数 >= 小顶堆元素数
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

插入时间复杂度$O(\log n)$，查询中位数$O(1)$。这个技巧同样适用于滑动窗口中位数、在线统计等场景。

题型四：贪心与堆的结合

LeetCode 621. 任务调度器

这道题需要安排任务执行顺序，使相同任务之间的最小间隔满足要求。贪心策略是：每次选择剩余次数最多的任务执行。

public int leastInterval(char[] tasks, int n) {
    int[] count = new int[26];
    for (char task : tasks) {
        count[task - 'A']++;
    }
    
    // 大顶堆，按剩余任务数排序
    PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
    for (int c : count) {
        if (c > 0) heap.offer(c);
    }
    
    int time = 0;
    while (!heap.isEmpty()) {
        List<Integer> temp = new ArrayList<>();
        // 执行一轮（n+1个时间片）
        for (int i = 0; i <= n; i++) {
            if (!heap.isEmpty()) {
                int cnt = heap.poll();
                if (cnt > 1) {
                    temp.add(cnt - 1);
                }
            }
            time++;
            if (heap.isEmpty() && temp.isEmpty()) {
                break;
            }
        }
        // 将剩余任务放回堆
        for (int cnt : temp) {
            heap.offer(cnt);
        }
    }
    
    return time;
}

这道题还有一种数学解法：结果为$\max(tasks.length, (maxFreq - 1) \times (n + 1) + maxCount)$。

题型五：会议室问题

LeetCode 253. 会议室 II

public int minMeetingRooms(int[][] intervals) {
    if (intervals == null || intervals.length == 0) return 0;
    
    // 按开始时间排序
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    
    // 小顶堆存储会议结束时间
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    
    for (int[] interval : intervals) {
        // 如果最早结束的会议已经结束，可以复用会议室
        if (!heap.isEmpty() && heap.peek() <= interval[0]) {
            heap.poll();
        }
        heap.offer(interval[1]);
    }
    
    return heap.size();
}

堆的大小就是需要的会议室数量。每个会议开始时，检查是否有会议室可以复用。

题型六：数据流第K大

LeetCode 703. 数据流中的第K大元素

class KthLargest {
    private PriorityQueue<Integer> heap;
    private int k;
    
    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.heap = new PriorityQueue<>();
        for (int num : nums) {
            add(num);
        }
    }
    
    public int add(int val) {
        heap.offer(val);
        if (heap.size() > k) {
            heap.poll();
        }
        return heap.peek();
    }
}

题型七：最后一块石头的重量

LeetCode 1046. 最后一块石头的重量

public int lastStoneWeight(int[] stones) {
    // 大顶堆
    PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
    for (int stone : stones) {
        heap.offer(stone);
    }
    
    while (heap.size() > 1) {
        int y = heap.poll();
        int x = heap.poll();
        if (x != y) {
            heap.offer(y - x);
        }
    }
    
    return heap.isEmpty() ? 0 : heap.peek();
}

堆与其他数据结构的对比

数据结构	插入	删除最值	查找	空间
无序数组	$O(1)$	$O(n)$	$O(n)$	$O(n)$
有序数组	$O(n)$	$O(1)$	$O(\log n)$	$O(n)$
堆	$O(\log n)$	$O(\log n)$	$O(n)$	$O(n)$
平衡BST	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$

堆在"只需要最值"的场景下是最优选择。但如果需要支持更多操作（如查找任意元素、范围查询），平衡二叉搜索树更合适。

什么时候选择堆

堆适合以下场景：

需要频繁获取最值：如任务调度、事件模拟
TopK问题：只需要前K个元素，不需要完整排序
数据流处理：持续插入、持续查询最值
合并有序序列：多路归并的效率关键

堆不适合以下场景：

需要随机访问：堆不支持高效查找任意元素
需要有序遍历：堆只能保证堆顶是最值，整体并非有序
内存受限且数据量大：需要考虑更紧凑的数据结构

引用

Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM.
Floyd, R. W. (1964). Algorithm 245: Treesort. Communications of the ACM.
Cormen, T. H., et al. Introduction to Algorithms, Chapter 6: Heapsort.
Java PriorityQueue Source Code
GeeksforGeeks - Binary Heap
VisuAlgo - Binary Heap Visualization
Princeton Algorithms - Priority Queues

完全二叉树的数组表示#

上浮与下沉：堆的两种核心操作#

上浮操作（Sift Up）#

下沉操作（Sift Down）#

为什么下沉后还需要上浮？#

建堆：O(n)的魔法#

Java中的PriorityQueue#

自定义对象的优先队列#

堆排序：被低估的排序算法#

LeetCode题型全解析#

题型一：TopK问题#

题型二：合并K个有序序列#

题型三：双堆技巧#

题型四：贪心与堆的结合#

题型五：会议室问题#

题型六：数据流第K大#

题型七：最后一块石头的重量#

堆与其他数据结构的对比#

什么时候选择堆#

引用#

更多精彩内容

排序算法为何如此重要从快速排序到TimSort的八十年演进与LeetCode完整通关指南

扫描线算法如何将二维问题降维成一维从天际线到矩形面积的LeetCode完整通关指南

最长公共子序列为何能解决十几类LeetCode问题从字符串相似度到DNA比对的动态规划精髓

博弈论算法为何能用数学公式预测胜负从Nim博弈到极大极小算法的完整LeetCode通关指南

链表算法为何让无数开发者头疼从指针陷阱到快慢指针的完整LeetCode通关指南