堆和优先队列

Posted Mar 24, 2025 Updated Dec 19, 2025

By Nomad

8 min read

堆和优先队列

堆的定义

堆是一种基于完全二叉树的数据结构，常用于实现优先队列。它分为两种类型：最大堆(父节点的值 ≥ 子节点）和 最小堆(父节点的值 ≤ 子节点）。

堆的特性

完全的二叉树结构

所有层除最后一层都是满的，最后一层节点从左到右填充
通过数组存储，父子节点下标关系
- - 父节点下标 parent(i) = (i-1)/2
- - 左子节点下标：leftChild(i) = 2*i + 1
- - 右子节点下标：rightChild(i) = 2*i + 2

堆的性质维护

上浮（Sift Up）插入元素时，从底部向上调整：如果它大于自己的父节点则与之交换，不断重复这一过程。
下沉（Sift Down）：删除堆顶时，将最后一个元素移到堆顶，向下调整：找到左子结点和右子结点的较大值与之交换(为了保证父节点大于子结点成立)，不断重复这一过程。

复杂度分析

插入和删除：O(log n)

因为堆是完全二叉树，假设堆中有 \(n\) 个元素，则堆的高度为 \(\lfloor \log_2 n \rfloor\)。
一个节点上浮或下沉最多需要 \(\lfloor \log_2 n \rfloor\)次操作。

构建堆：O(n)

堆构建采用自底向上的方法，从最后一个非叶子节点开始，依次向前调整子树，使其满足堆的性质。数组的最有一个非叶节点的下标为 ⌊n/2⌋ - 1，对每个非叶子节点执行下沉（Sift Down）操作，将其调整到合适位置。

精确的数学推导

假设堆的高度 \(h = \lfloor log_2 n \lfloor\),节点按层分布如下：

第k层（从 0 开始计数）的节点数为 2k。
第k层节点的最大下沉次数为h-k

总时间复杂度的计算所有节点的下沉次数之和为

\[T(n)=\sum_{k=0}^{h}(第k层节点数)*(下沉次数)=\sum_{k=0}^{h} 2^k * (h-k)\]

令 i=h−k，则 k=h−i，且当 k 从 0 到 h 时，i 从 h 到 0。公式可改写为：

\[T(n)=\sum_{i=0}^{h} 2^{h-i} * i = 2^h*\sum_{i=0}^{h} \frac{i}{2^i}\]

已知几何级数求和公式：

\[\sum_{i=0}^{\infty} \frac{i}{2^i}= 2(收敛值)\]

当\(h \to \infty\)时,级数收敛到2.因此:

\[\sum_{i=0}^{h} \frac{i}{2^i} \leq 2 \implies T(n) \leq 2^h*2\]

由\(h=log_2 n\),得:

\[2^h=2^{log_2 n}=n \implies T(n)\leq2n\]

因此,总时间复杂度为\(T(n)=O(n)\)

使用场景

1. 优先队列（Priority Queue）

堆是实现优先队列的核心数据结构，支持快速插入和删除最高/最低优先级元素。

2.堆排序（Heap Sort）

利用堆的极值特性实现排序，时间复杂度为 O(n log n)。

3. Top-K 问题

在大量数据中快速找到前K个最大/最小元素。

实现方法

找最大Top-K：维护一个最小堆，堆顶为当前K个元素中的最小值。

找最小Top-K：维护一个最大堆，堆顶为当前K个元素中的最大值。

优势：时间复杂度 O(n log K)，优于完全排序的 O(n log n)。

4. 合并多个有序序列

高效合并多个已排序的数组/链表。

实现方法

将所有序列的第一个元素加入最小堆
每次取出堆顶元素,并将该元素的下一个元素加入堆

5.中位数维护

动态维护数据流的中位数（无需存储全部数据）。

实现方法

用两个堆：最大堆存较小的一半数，最小堆存较大的一半数。
保证两个堆的大小差 ≤1，中位数由堆顶计算得出。

堆的实现(java)

  
package Heap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

//最大堆，如果要实现最小堆修改comparator
public class Heap<T> {
    private final List<T> heap;
    private final Comparator<? super T> comparator;

    // 使用自然顺序的构造函数
    public Heap() {
        this.heap = new ArrayList<>();
        comparator = null;
    }

    // 自定义比较器的构造函数
    public Heap(Comparator<? super T> comparator) {
        this.heap = new ArrayList<>();
        this.comparator = comparator;
    }

    public Heap(List<T> list, Comparator<? super T> comparator) {
        this.comparator = comparator;
        int size = list.size();
        heap  = list;
        for(int i = size/2-1; i >= 0; i--) {
            siftDown(i);
        }
    }

    // 插入元素
    public void insert(T value) {
        heap.add(value);
        siftUp(heap.size() - 1);
    }

    // 删除堆顶元素
    public T remove() {
        if (isEmpty()) throw new IllegalStateException("Heap is empty");
        T root = heap.getFirst();
        int lastIndex = heap.size() - 1;
        heap.set(0, heap.get(lastIndex));
        heap.remove(lastIndex);
        siftDown(0);
        return root;
    }

    public T peek() {
        if (isEmpty()) throw new IllegalStateException("Heap is empty");
        return heap.getfirst();
    }

    // 上浮操作
    private void siftUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (compare(heap.get(index), heap.get(parent)) <= 0) break;
            swap(index, parent);
            index = parent;
        }
    }

    // 下沉操作
    private void siftDown(int index) {
        int size = heap.size();
        while (true) {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int extreme = index; // 最大堆找更大值，最小堆找更小值

            if (left < size && compare(heap.get(left), heap.get(extreme)) > 0) {
                extreme = left;
            }
            if (right < size && compare(heap.get(right), heap.get(extreme)) > 0) {
                extreme = right;
            }
            if (extreme == index) break;

            swap(index, extreme);
            index = extreme;
        }
    }

    // 比较两个元素
    private int compare(T a, T b) {
        if (comparator != null) {
            return comparator.compare(a, b);
        } else {
            @SuppressWarnings("unchecked")
            Comparable<? super T> comparable = (Comparable<? super T>) a;
            return comparable.compareTo(b);
        }
    }

    // 交换元素
    private void swap(int i, int j) {
        T temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    public boolean isEmpty() {
        return heap.isEmpty();
    }

    public int size() {
        return heap.size();
    }

}