数据结构

二叉堆

最后修改:

1、优先级队列是一种能够自动排序的数据结构，增删元素的复杂度是 O(logN)，底层使用二叉堆实现。

2、二叉堆是一种拥有特殊性质的完全二叉树。

3、优先级队列（二叉堆）的核心方法是 swim（上浮）, sink（下沉），用来维护二叉堆的性质。

二叉堆的核心性质

二叉堆是“完全二叉树”的延伸，本质是通过数组实现的逻辑二叉树，核心性质围绕“堆序性”和“结构完整性”展开：

  1. 结构性质：完全二叉树

    • 物理存储为数组，逻辑结构是完全二叉树——除最后一层外，每一层节点数均为最大值，最后一层节点从左到右连续排列（无空缺）。
    • 数组与二叉树映射规则（索引从 0 开始）：
      • 左子节点索引 = 2*i + 1
      • 右子节点索引 = 2*i + 2
      • 父节点索引 = (i - 1) / 2（整数除法）
    • 堆的高度始终为 O(logN)（N 为节点总数），为高效操作提供基础。

  2. 堆序性质：父节点优先级高于子节点

    • 分为两种类型：
      • 大顶堆：每个父节点的值 ≥ 左右子节点的值（堆顶为最大值）；
      • 小顶堆：每个父节点的值 ≤ 左右子节点的值（堆顶为最小值）。
    • 堆序性是所有操作的核心依据，动态调整均为维持该性质。

  3. 核心操作：sink（下沉）与 swim（上浮）

    • 所有堆操作（插入、删除堆顶等）均依赖这两个基础操作，用于恢复堆序性：
      • swim（上浮）：新插入节点破坏堆序时（如小顶堆中节点值小于父节点），向上与父节点交换，直到满足堆序；
      • sink（下沉）：堆顶节点替换后破坏堆序时（如大顶堆中堆顶值小于子节点），向下与优先级更高的子节点交换，直到满足堆序。

最常见的应用：优先级队列（Priority Queue）

优先级队列是二叉堆的核心应用，本质是“按优先级排序的队列”——出队顺序由元素优先级决定，而非插入顺序，依赖二叉堆的高效调整能力。

核心特性

  • 核心操作：
    • 插入元素（insert）：将元素加入堆尾，通过 swim 调整位置；
    • 取出优先级最高元素（extract-max/extract-min）：取出堆顶元素，将堆尾元素移至堆顶，通过 sink 调整位置。
  • 时间复杂度：插入和取出操作均为 O(logN)，远优于普通数组/链表的 O(N)。

底层实现逻辑（基于二叉堆）

以大顶堆为例：

  1. 插入元素：新元素追加到数组末尾（完全二叉树最后一个节点），若大于父节点则执行 swim 上浮，恢复大顶堆性质；
  2. 取出最大元素：堆顶与数组末尾元素交换，删除原堆顶（数组末尾），对新堆顶执行 sink 下沉，恢复大顶堆性质。

典型使用场景

  • 任务调度（如操作系统按优先级分配 CPU 资源）；
  • 最短路径算法（如 Dijkstra 算法快速获取最短路径节点）；
  • 海量数据 Top K 问题（如快速找出 N 个数中最大的 K 个）。

另一种应用：堆排序（Heap Sort）

堆排序是基于二叉堆的排序算法，核心思路是“利用堆序性，依次提取堆顶元素构建有序序列”，时间复杂度为 O(NlogN)。

核心步骤

  1. 构建堆（Heapify）：将无序数组转换为大顶堆（或小顶堆）。
    • 从最后一个非叶子节点（索引 N/2 - 1）开始，依次对每个节点执行 sink 下沉，直到数组满足堆序性。
  2. 排序阶段：反复提取堆顶元素，构建有序序列。
    • 堆顶（当前最大值）与数组末尾元素交换，末尾为已排序最大值；
    • 缩小堆范围（排除已排序元素），对新堆顶执行 sink 下沉，恢复堆序性；
    • 重复操作，直到堆范围为 0，数组即为升序序列。

关键特性

  • 原地排序：仅需常数级额外空间；
  • 不稳定排序：相等元素相对位置可能改变；
  • 时间复杂度：构建堆 O(N) + 排序阶段 O(NlogN)，整体 O(NlogN)。

对比优势

  • 无需额外空间（区别于归并排序），最坏情况下仍保持 O(NlogN) 复杂度（区别于快速排序）；
  • 适合海量数据或内存受限场景，核心优势是高效的元素筛选能力。

二叉堆/优先级队列 C++ 实现

简化版优先级队列

核心思路

简化版优先级队列的核心在于理解二叉堆的两个关键操作：上浮（swim） 和 下沉（sink）。这些操作维护了堆的性质，确保堆顶元素始终是最大值（最大堆）或最小值（最小堆）。

难点分析

  1. 数组索引计算：在数组中模拟完全二叉树时，需要正确计算父节点和子节点的索引
  2. 边界条件处理：在 swim 和 sink 操作中要避免数组越界
  3. 堆性质维护：每次插入或删除后都要通过 swim/sink 操作重新维护堆的有序性

增：push/swim 方法插入元素

插入流程：

  1. 将新元素添加到数组末尾
  2. 通过 swim 操作将其上浮到正确位置

swim 操作原理：

  • 比较当前节点与其父节点的值
  • 如果当前节点违反堆性质（最大堆中比父节点大），则交换位置
  • 继续向上比较，直到到达根节点或满足堆性质

删：pop/sink 方法删除元素

删除流程（通常删除堆顶元素）：

  1. 将堆顶元素与数组最后一个元素交换
  2. 删除数组最后一个元素（原堆顶）
  3. 通过 sink 操作将新的堆顶元素下沉到正确位置

sink 操作原理：

  • 比较当前节点与其左右子节点的值
  • 在最大堆中，如果当前节点小于较大的子节点，则与该子节点交换
  • 继续向下比较，直到成为叶子节点或满足堆性质

查：peek 方法查看堆顶元素

直接返回数组的第一个元素（索引为0或1，取决于实现），时间复杂度 O(1)。

在数组上模拟二叉树

完全二叉树可以用数组高效表示：

如果根节点索引为 0：

  • 父节点索引：parent(i) = (i - 1) / 2
  • 左子节点索引：left(i) = 2 * i + 1
  • 右子节点索引：right(i) = 2 * i + 2

如果根节点索引为 1：

  • 父节点索引：parent(i) = i / 2
  • 左子节点索引：left(i) = 2 * i
  • 右子节点索引：right(i) = 2 * i + 1

C++ 实现通常使用索引从 0 开始的方式。

代码实现

简化版优先级队列（最大堆）

  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
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

#include <vector>
#include <stdexcept>
#include <iostream>
#include <cassert>

template<typename T>
class SimplePriorityQueue {
private:
    std::vector<T> heap;
    
    // 获取父节点索引
    int parent(int i) { return (i - 1) / 2; }
    
    // 获取左子节点索引
    int left(int i) { return 2 * i + 1; }
    
    // 获取右子节点索引
    int right(int i) { return 2 * i + 2; }
    
    // 上浮操作
    void swim(int i) {
        while (i > 0 && heap[i] > heap[parent(i)]) {
            std::swap(heap[i], heap[parent(i)]);
            i = parent(i);
        }
    }
    
    // 下沉操作
    void sink(int i) {
        int n = heap.size();
        while (left(i) < n) {
            int maxChild = left(i);
            // 找到较大的子节点
            if (right(i) < n && heap[right(i)] > heap[left(i)]) {
                maxChild = right(i);
            }
            
            // 如果当前节点已经大于等于较大子节点，停止下沉
            if (heap[i] >= heap[maxChild]) {
                break;
            }
            
            std::swap(heap[i], heap[maxChild]);
            i = maxChild;
        }
    }

public:
    // 插入元素
    void push(const T& val) {
        heap.push_back(val);
        swim(heap.size() - 1);
    }
    
    // 删除并返回堆顶元素
    T pop() {
        if (heap.empty()) {
            throw std::runtime_error("Priority queue is empty");
        }
        
        T top = heap[0];
        std::swap(heap[0], heap[heap.size() - 1]);
        heap.pop_back();
        
        if (!heap.empty()) {
            sink(0);
        }
        
        return top;
    }
    
    // 查看堆顶元素
    T peek() const {
        if (heap.empty()) {
            throw std::runtime_error("Priority queue is empty");
        }
        return heap[0];
    }
    
    // 检查是否为空
    bool empty() const {
        return heap.empty();
    }
    
    // 获取元素数量
    size_t size() const {
        return heap.size();
    }
};

void test_basic_operations() {
    std::cout << "Testing basic operations..." << std::endl;
    SimplePriorityQueue<int> pq;
    
    assert(pq.empty());
    assert(pq.size() == 0);
    
    pq.push(10);
    assert(!pq.empty());
    assert(pq.size() == 1);
    assert(pq.peek() == 10);
    
    pq.push(30);
    assert(pq.peek() == 30); // Max heap property
    
    pq.push(20);
    assert(pq.peek() == 30);
    
    pq.push(40);
    assert(pq.peek() == 40);
    
    std::cout << "  Push operations passed." << std::endl;
    
    assert(pq.pop() == 40);
    assert(pq.peek() == 30);
    
    assert(pq.pop() == 30);
    assert(pq.peek() == 20);
    
    assert(pq.pop() == 20);
    assert(pq.peek() == 10);
    
    assert(pq.pop() == 10);
    assert(pq.empty());
    
    std::cout << "  Pop operations passed." << std::endl;
}

void test_random_order() {
    std::cout << "Testing random order insertion..." << std::endl;
    SimplePriorityQueue<int> pq;
    std::vector<int> inputs = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    for(int x : inputs) {
        pq.push(x);
    }
    
    std::vector<int> expected = {9, 6, 5, 5, 4, 3, 2, 1, 1};
    std::vector<int> result;
    while(!pq.empty()) {
        result.push_back(pq.pop());
    }
    
    assert(result == expected);
    std::cout << "  Random order sort passed." << std::endl;
}

void test_exceptions() {
    std::cout << "Testing exceptions..." << std::endl;
    SimplePriorityQueue<int> pq;
    try {
        pq.pop();
        assert(false && "Should have thrown exception");
    } catch (const std::runtime_error& e) {
        std::cout << "  Caught expected exception on pop(): " << e.what() << std::endl;
    }
    
    try {
        pq.peek();
        assert(false && "Should have thrown exception");
    } catch (const std::runtime_error& e) {
        std::cout << "  Caught expected exception on peek(): " << e.what() << std::endl;
    }
}

int main() {
    try {
        test_basic_operations();
        test_random_order();
        test_exceptions();
        
        std::cout << "\nAll tests passed successfully!" << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Test failed with exception: " << e.what() << std::endl;
        return 1;
    }
    
    return 0;
}

完善版优先级队列

完善版优先级队列支持自定义比较器，可以实现最大堆、最小堆或任何自定义优先级规则。

  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
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

#include <vector>
#include <functional>
#include <stdexcept>

template<typename T, typename Compare = std::less<T>>
class PriorityQueue {
private:
    std::vector<T> heap;
    Compare comp; // 比较器
    
    // 获取父节点索引
    int parent(int i) const { return (i - 1) / 2; }
    
    // 获取左子节点索引
    int left(int i) const { return 2 * i + 1; }
    
    // 获取右子节点索引
    int right(int i) const { return 2 * i + 2; }
    
    // 上浮操作
    void swim(int i) {
        while (i > 0 && comp(heap[parent(i)], heap[i])) {
            std::swap(heap[i], heap[parent(i)]);
            i = parent(i);
        }
    }
    
    // 下沉操作
    void sink(int i) {
        int n = heap.size();
        while (left(i) < n) {
            int maxChild = left(i);
            // 使用比较器找到应该上浮的子节点
            if (right(i) < n && comp(heap[maxChild], heap[right(i)])) {
                maxChild = right(i);
            }
            
            // 如果当前节点已经满足堆性质，停止下沉
            if (!comp(heap[i], heap[maxChild])) {
                break;
            }
            
            std::swap(heap[i], heap[maxChild]);
            i = maxChild;
        }
    }

public:
    // 构造函数
    explicit PriorityQueue(const Compare& c = Compare()) : comp(c) {}
    
    // 插入元素
    void push(const T& val) {
        heap.push_back(val);
        swim(heap.size() - 1);
    }
    
    // 删除并返回堆顶元素
    T pop() {
        if (heap.empty()) {
            throw std::runtime_error("Priority queue is empty");
        }
        
        T top = heap[0];
        std::swap(heap[0], heap[heap.size() - 1]);
        heap.pop_back();
        
        if (!heap.empty()) {
            sink(0);
        }
        
        return top;
    }
    
    // 查看堆顶元素
    const T& top() const {
        if (heap.empty()) {
            throw std::runtime_error("Priority queue is empty");
        }
        return heap[0];
    }
    
    // 检查是否为空
    bool empty() const {
        return heap.empty();
    }
    
    // 获取元素数量
    size_t size() const {
        return heap.size();
    }
    
    // 清空队列
    void clear() {
        heap.clear();
    }
};

// 使用示例
#include <iostream>

int main() {
    // 最大堆（默认）
    PriorityQueue<int> maxHeap;
    maxHeap.push(3);
    maxHeap.push(1);
    maxHeap.push(4);
    maxHeap.push(1);
    maxHeap.push(5);
    
    std::cout << "Max Heap: ";
    while (!maxHeap.empty()) {
        std::cout << maxHeap.pop() << " "; // 输出: 5 4 3 1 1
    }
    std::cout << std::endl;
    
    // 最小堆
    PriorityQueue<int, std::greater<int>> minHeap;
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(1);
    minHeap.push(5);
    
    std::cout << "Min Heap: ";
    while (!minHeap.empty()) {
        std::cout << minHeap.pop() << " "; // 输出: 1 1 3 4 5
    }
    std::cout << std::endl;
    
    return 0;
}

关键特性总结

  1. 时间复杂度：

    • 插入（push）：O(log N)
    • 删除（pop）：O(log N)
    • 查看堆顶（peek/top）：O(1)

  2. 空间复杂度：O(N)

  3. 灵活性：通过自定义比较器可以实现各种优先级策略

  4. 稳定性：标准库的 std::priority_queue 也是基于二叉堆实现的

Reference

https://labuladong.online/algo/data-structure-basic/binary-heap-basic/

© 2025 - 2026 山重水复疑无路，柳暗花明又一村
山重水复疑无路，柳暗花明又一村
使用 Hugo 构建
主题 Stack 由 Jimmy 设计