Skip to content

优先队列（堆）

一、ADT模型与核心操作

1. 抽象数据类型定义

对象：包含零个或多个元素的集合，每个元素有优先级标识。
核心操作：

操作 功能说明 时间复杂度目标
Initialize 初始化空队列 O(1)
Insert 插入元素并维护优先级结构 O(log N)
DeleteMin/DeleteMax 删除并返回最高优先级元素 O(log N)
FindMin/FindMax 查询最高优先级元素（不删除） O(1)

二、简单实现方案对比

1. 不同数据结构的时间复杂度

实现方式 插入 删除极值 适用场景
无序数组 O(1) O(N) 删除操作极少
有序数组 O(N) O(1) 频繁删除，极少插入
二叉搜索树 O(log N) O(log N) 需要动态平衡
二叉堆 O(log N) O(log N) 综合性能最优（默认选择）

三、二叉堆（Binary Heap）详解

1. 结构属性

  • 完全二叉树：所有层除最后一层外必须填满，最后一层从左到右填充。
  • 数组存储：索引从1开始，索引0为哨兵（存储极小值）。
    • 节点 i 的父节点：i/2（向下取整）
    • 节点 i 的子节点：左子 2*i，右子 2*i+1。

示例数组与树的对应关系：

索引：0 |1 |2 |3 |4 |5 |6  
值： -∞ |2 |3 |8 |5 |6 |9  
对应的树结构：  
        2  
      /   \  
     3     8  
    / \   /  
   5   6 9

2. 堆序属性

  • 最小堆：任意节点的值 ≤ 子节点的值（根为最小值）。
  • 最大堆：任意节点的值 ≥ 子节点的值（根为最大值）。

Example

(FDS HW6)在一个包含 \(n\)（\(n > 1\)）个元素的最大堆中，最小键值的数组索引可能是_______。

  • A. 1
  • B. \(\left\lfloor \frac{n}{2} \right\rfloor - 1\)
  • C. \(\left\lfloor \frac{n}{2} \right\rfloor\)
  • D. \(\left\lfloor \frac{n}{2} \right\rfloor + 2\)

这个题有一种很快的解法，因为最大堆的性质保证了越往下的子节点越小，那选索引最大的就好了。

要是具体思路分析的话，可以这么理解：叶子节点位于数组后半段；若非子节点包含最小值，则其子节点必须更小，违反最大堆定义。

3. 核心操作实现

3.1 插入（Insert）

步骤：
1. 新元素插入数组末尾（维持完全二叉树结构）。
2. 上滤（Percolate Up）：与父节点比较，若更小则交换，直到满足堆序。

代码实现：

void Insert(ElementType X, PriorityQueue H) {  
    if (IsFull(H)) return Error;  
    int i = ++H->Size;  
    // 上滤：父节点 > X 时，父节点下移  
    for (; H->Elements[i/2] > X; i /= 2)  
        H->Elements[i] = H->Elements[i/2];  
    H->Elements[i] = X;  
}

分步示例：插入元素 1

初始堆：[-∞, 2, 3, 8, 5, 6, 9]  
插入1到末尾 → 索引7 → 与父节点8交换 → 再与父节点2交换 → 最终堆：[-∞, 1, 2, 8, 5, 6, 9, 3]

3.2 删除最小值（DeleteMin）

步骤：
1. 取出根节点（最小值）。
2. 将末尾元素移至根位置。
3. 下滤（Percolate Down）：与较小的子节点交换，直到满足堆序。

代码实现：

ElementType DeleteMin(PriorityQueue H) {  
    if (IsEmpty(H)) return Error;  
    ElementType Min = H->Elements[1];  
    ElementType Last = H->Elements[H->Size--];  
    int i, Child;  
    for (i=1; i*2 <= H->Size; i=Child) {  
        Child = i*2;  
        // 选择较小的子节点  
        if (Child != H->Size && H->Elements[Child+1] < H->Elements[Child])  
            Child++;  
        if (Last > H->Elements[Child])  
            H->Elements[i] = H->Elements[Child];  
        else break;  
    }  
    H->Elements[i] = Last;  
    return Min;  
}

分步示例：删除根节点 1

取出1 → 末尾元素3移至根 → 3与子节点2交换 → 最终堆：[-∞, 2, 3, 8, 5, 6, 9]

4. 其他操作

操作 实现方式 时间复杂度
BuildHeap 从最后一个非叶子节点开始下滤 O(N)
DecreaseKey 降低某节点值后上滤 O(log N)
IncreaseKey 增加某节点值后下滤 O(log N)
Delete 先DecreaseKey再DeleteMin O(log N)

四、时间复杂度分析

1. 操作复杂度对比

操作 普通实现 二叉堆 d堆（d=3）
Insert O(1)/O(N) O(log N) O(log₃ N)
DeleteMin O(N) O(log N) O(3 log₃ N)

2. 构建堆的时间复杂度证明

定理：对高度为h的完美二叉树，节点高度和为 \(2^{h+1} - (h+2)\)。

  • 推导：
    • 第k层有 \(2^k\) 个节点，每个节点高度为 \(h - k\)。
    • 总高度和：\(\sum_{k=0}^h 2^k (h - k) = O(N)\)。

五、d-堆（d-ary Heap）

1. 特点

  • 每个节点有d个子节点，树高降低为 \(\log_d N\)。
  • 插入更快：上滤路径更短。
  • 删除更慢：需比较d个子节点找最小值。

2. 代码调整

// 下滤时选择子节点范围：d*i - (d-2) 到 d*i +1  
for (int j = d*i - (d-2); j <= d*i +1; j++) {  
    if (H->Elements[j] < minChild) {  
        minChild = H->Elements[j];  
        child = j;  
    }  
}

六、总结

特性 二叉堆优势 适用场景
插入/删除效率 O(log N) 稳定 动态数据流
空间复杂度 数组存储，无指针开销 内存受限环境
扩展性 支持DecreaseKey等复杂操作 图算法、实时系统