第五章基础数据结构¶

数据结构是算法的基石。掌握栈、队列、链表、哈希表、堆等基础数据结构，是解决各类算法问题的前提。

5.1 栈（Stack）¶

5.1.1 基本概念¶

栈是一种后进先出（LIFO, Last In First Out）的线性数据结构。只能在栈顶进行插入（push）和删除（pop）操作。

graph TD
    subgraph 栈的操作示意
        direction TB
        A["入栈 push(1)"] --> B["栈: [1]"]
        B --> C["入栈 push(2)"]
        C --> D["栈: [1, 2]"]
        D --> E["入栈 push(3)"]
        E --> F["栈: [1, 2, 3]  ← 栈顶"]
        F --> G["出栈 pop() → 3"]
        G --> H["栈: [1, 2]  ← 栈顶"]
    end

5.1.2 数组实现栈¶

用数组模拟栈，维护一个栈顶指针 top。

#include <iostream>
using namespace std;

const int MAXN = 100010;  // 栈的最大容量

int stk[MAXN];  // 用数组存储栈元素
int top_idx = 0;  // 栈顶指针，指向下一个可插入的位置

// 入栈操作：将元素 x 压入栈顶
void push(int x) {
    stk[top_idx++] = x;
}

// 出栈操作：弹出栈顶元素
void pop() {
    if (top_idx > 0) {
        top_idx--;
    }
}

// 获取栈顶元素
int peek() {
    return stk[top_idx - 1];
}

// 判断栈是否为空
bool empty() {
    return top_idx == 0;
}

// 获取栈的大小
int size() {
    return top_idx;
}

时间复杂度分析：

操作	时间复杂度	说明
push	O(1)	直接赋值
pop	O(1)	移动指针
peek	O(1)	直接访问
empty	O(1)	比较操作

5.1.3 链表实现栈¶

用单链表实现栈，每次在链表头部插入和删除。

// 链表节点结构
struct Node {
    int val;      // 节点值
    Node* next;   // 指向下一个节点
    Node(int v) : val(v), next(nullptr) {}
};

Node* head = nullptr;  // 链表头节点（即栈顶）
int sz = 0;  // 栈的大小

// 入栈：在链表头部插入新节点
void push(int x) {
    Node* newNode = new Node(x);
    newNode->next = head;
    head = newNode;
    sz++;
}

// 出栈：删除链表头节点
void pop() {
    if (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;  // 释放内存
        sz--;
    }
}

// 获取栈顶元素
int peek() {
    return head->val;
}

// 判断栈是否为空
bool empty() {
    return head == nullptr;
}

5.1.4 STL stack 用法¶

C++ STL 提供了 stack 容器适配器。

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;

    // 入栈
    s.push(1);
    s.push(2);
    s.push(3);

    // 栈顶元素
    cout << "栈顶: " << s.top() << endl;  // 输出 3

    // 出栈
    s.pop();
    cout << "出栈后栈顶: " << s.top() << endl;  // 输出 2

    // 大小和判空
    cout << "大小: " << s.size() << endl;    // 输出 2
    cout << "是否为空: " << s.empty() << endl;  // 输出 0 (false)

    return 0;
}

竞赛中的栈

在竞赛中，最常用的不是 STL stack，而是用数组模拟栈。数组模拟速度更快，且方便调试。很多题目中，栈的思想用来匹配括号、计算表达式、维护单调性等。

5.2 单调栈¶

5.2.1 原理¶

单调栈是一种特殊的栈，栈内元素保持单调递增或单调递减的顺序。当新元素入栈时，需要弹出所有破坏单调性的元素。

graph LR
    subgraph 单调递减栈示例 - 维护"下一个更大元素"
        A["数组: 2 1 2 4 3"] --> B["过程演示"]
        B --> C["i=0: 栈[2]"]
        C --> D["i=1: 栈[2,1]"]
        D --> E["i=2: 弹出1→ans[1]=2, 弹出2→ans[0]=2, 栈[2]"]
        E --> F["i=3: 弹出2→ans[2]=4, 栈[4]"]
        F --> G["i=4: 栈[4,3]"]
    end

核心思想：维护一个栈，使得栈中的元素从栈底到栈顶满足某种单调性。每加入一个新元素时，不断弹出栈顶不满足单调性的元素，并在此过程中解决相关问题。

5.2.2 经典应用一：下一个更大元素¶

给定一个数组，对于每个元素，找到右边第一个比它大的元素。

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

// 求每个元素右边第一个比它大的元素
// nums: 输入数组
// 返回: 结果数组，res[i] 表示 nums[i] 右边第一个比它大的元素，没有则为 -1
vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);   // 初始化结果为 -1
    stack<int> st;             // 单调递减栈，存储下标

    for (int i = 0; i < n; i++) {
        // 当前元素比栈顶元素大，说明找到了栈顶元素的"下一个更大元素"
        while (!st.empty() && nums[st.top()] < nums[i]) {
            res[st.top()] = nums[i];  // 记录结果
            st.pop();                  // 弹出已处理的元素
        }
        st.push(i);  // 将当前下标入栈
    }
    return res;
}

int main() {
    vector<int> nums = {2, 1, 2, 4, 3};
    vector<int> res = nextGreaterElement(nums);
    // 输出: 4 2 4 -1 -1
    for (int x : res) cout << x << " ";
    cout << endl;
    return 0;
}

时间复杂度： O(n)，每个元素最多入栈一次、出栈一次。

5.2.3 经典应用二：柱状图中最大的矩形（LeetCode 84）¶

这是单调栈的经典难题。对于每个柱子，需要找到左边和右边第一个比它矮的柱子，从而确定以该柱子为高度的最大矩形宽度。

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

// 求柱状图中最大的矩形面积
// heights: 每个柱子的高度
// 返回: 最大矩形面积
int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    stack<int> st;  // 单调递增栈，存储下标
    int maxArea = 0;

    for (int i = 0; i <= n; i++) {
        // 当前高度小于栈顶高度时，计算以栈顶为高度的矩形面积
        int curHeight = (i == n) ? 0 : heights[i];
        while (!st.empty() && heights[st.top()] > curHeight) {
            int h = heights[st.top()];  // 矩形高度
            st.pop();
            // 宽度 = 右边界(i) - 左边界(新栈顶+1)
            int w = st.empty() ? i : (i - st.top() - 1);
            maxArea = max(maxArea, h * w);
        }
        st.push(i);
    }
    return maxArea;
}

int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << "最大矩形面积: " << largestRectangleArea(heights) << endl;
    // 输出: 10
    return 0;
}

时间复杂度： O(n)

单调栈的关键

使用单调栈时，注意栈中存储的是下标而非值，这样方便计算区间宽度。

5.3 队列（Queue）¶

5.3.1 基本概念¶

队列是一种先进先出（FIFO, First In First Out）的线性数据结构。只能在一端（队尾）插入，在另一端（队头）删除。

graph LR
    subgraph 队列操作示意
        A["入队 1"] --> B["队列: 1"]
        B --> C["入队 2"]
        C --> D["队列: 1 2"]
        D --> E["入队 3"]
        E --> F["队列: 1 2 3"]
        F --> G["出队 → 1"]
        G --> H["队列: 2 3"]
    end

5.3.2 循环队列¶

用数组实现队列时，直接使用两个指针（队头 front、队尾 rear）会导致空间浪费。循环队列通过取模运算让数组"首尾相连"，充分利用空间。

#include <iostream>
using namespace std;

const int MAXN = 100010;  // 队列最大容量

int q[MAXN];    // 存储队列元素
int head = 0;   // 队头指针
int tail = 0;   // 队尾指针（指向下一个可插入的位置）

// 入队：将元素 x 加入队尾
void push(int x) {
    q[tail] = x;
    tail = (tail + 1) % MAXN;  // 循环取模
}

// 出队：弹出队头元素
void pop() {
    head = (head + 1) % MAXN;
}

// 获取队头元素
int front() {
    return q[head];
}

// 判断队列是否为空
bool empty() {
    return head == tail;
}

// 获取队列大小
int size() {
    return (tail - head + MAXN) % MAXN;
}

5.3.3 STL queue 和 deque¶

#include <iostream>
#include <queue>
#include <deque>
using namespace std;

int main() {
    // ===== queue: 普通队列 =====
    queue<int> qu;
    qu.push(1);
    qu.push(2);
    qu.push(3);
    cout << "队头: " << qu.front() << endl;  // 1
    qu.pop();
    cout << "出队后队头: " << qu.front() << endl;  // 2

    // ===== deque: 双端队列 =====
    // 双端队列两端都可以进行插入和删除操作
    deque<int> dq;
    dq.push_back(1);   // 从尾部插入
    dq.push_front(2);  // 从头部插入 → dq: [2, 1]
    dq.push_back(3);   // 从尾部插入 → dq: [2, 1, 3]

    cout << "头部: " << dq.front() << endl;  // 2
    cout << "尾部: " << dq.back() << endl;   // 3

    dq.pop_front();  // 弹出头部 → dq: [1, 3]
    dq.pop_back();   // 弹出尾部 → dq: [1]

    return 0;
}

deque 的双重身份

deque 既可以当队列用，也可以当栈用。在竞赛中，单调队列通常用 deque 实现。

5.4 单调队列¶

5.4.1 原理¶

单调队列是一种特殊的双端队列（deque），队列中的元素保持单调性。常用于解决滑动窗口问题。

核心操作：

维护一个双端队列 dq
新元素入队前，从队尾弹出所有比它大（或小）的元素
检查队头元素是否已经滑出窗口，若是则从队头弹出
队头元素始终是当前窗口的最值

graph TD
    subgraph 滑动窗口最大值示例
        A["数组: 1 3 -1 -3 5 3 6 7, 窗口大小 k=3"] --> B["i=0: dq=[0], 窗口未满"]
        B --> C["i=1: 弹出0, dq=[1], 窗口未满"]
        C --> D["i=2: dq=[1,2], 窗口[1,3,-1], max=3"]
        D --> E["i=3: dq=[1,2,3], 窗口[3,-1,-3], max=3"]
        E --> F["i=4: 弹出3,2,1, dq=[4], 窗口[-1,-3,5], max=5"]
        F --> G["i=5: dq=[4,5], 窗口[-3,5,3], max=5"]
    end

5.4.2 滑动窗口最大值（LeetCode 239）¶

给定数组和窗口大小 k，返回每个滑动窗口中的最大值。

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

// 求滑动窗口中的最大值
// nums: 输入数组
// k: 窗口大小
// 返回: 每个窗口的最大值
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;         // 存储下标，维护单调递减队列
    vector<int> res;

    for (int i = 0; i < nums.size(); i++) {
        // 1. 检查队头是否已滑出窗口
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // 2. 从队尾弹出比当前元素小的元素（维护单调递减）
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }

        // 3. 将当前下标加入队尾
        dq.push_back(i);

        // 4. 窗口形成后，记录队头（最大值）
        if (i >= k - 1) {
            res.push_back(nums[dq.front()]);
        }
    }
    return res;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    vector<int> res = maxSlidingWindow(nums, 3);
    // 输出: 3 3 5 5 6 7
    for (int x : res) cout << x << " ";
    cout << endl;
    return 0;
}

时间复杂度： O(n)，每个元素最多入队一次、出队一次。

单调队列 vs 单调栈

单调栈：解决"下一个更大/更小元素"类问题
单调队列：解决"滑动窗口最值"类问题
两者的核心思想相同：维护单调性，淘汰不可能成为答案的元素

5.5 链表¶

5.5.1 单链表¶

单链表是最基本的链表结构，每个节点包含一个值和一个指向下一个节点的指针。

graph LR
    A["head"] --> B["1|→"] --> C["2|→"] --> D["3|→"] --> E["NULL"]

竞赛常用写法：用数组模拟链表（静态链表）

#include <iostream>
using namespace std;

const int MAXN = 100010;

// 静态链表实现
// e[i]: 节点 i 存储的值
// ne[i]: 节点 i 的 next 指针指向的节点下标
// head: 头节点下标
// idx: 当前已使用的节点数（下一个可用节点的下标）
int e[MAXN], ne[MAXN];
int head, idx;

// 初始化链表
void init() {
    head = -1;  // -1 表示 NULL
    idx = 0;
}

// 在链表头部插入值为 x 的节点
void addHead(int x) {
    e[idx] = x;       // 存储值
    ne[idx] = head;   // 新节点的 next 指向原头节点
    head = idx;       // 更新头节点
    idx++;
}

// 在第 k 个插入的节点后面插入值为 x 的节点
void addAfter(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];  // 新节点的 next 指向 k 的 next
    ne[k] = idx;       // k 的 next 指向新节点
    idx++;
}

// 删除第 k 个插入的节点后面的节点
void removeAfter(int k) {
    ne[k] = ne[ne[k]];  // 跳过被删除的节点
}

// 遍历链表
void print() {
    for (int i = head; i != -1; i = ne[i]) {
        cout << e[i] << " ";
    }
    cout << endl;
}

5.5.2 双链表¶

双链表的每个节点有前驱和后继指针，可以双向遍历。

graph LR
    A["NULL ←"] --> B["1|⇔"] --> C["2|⇔"] --> D["3|⇔"] --> E["→ NULL"]

#include <iostream>
using namespace std;

const int MAXN = 100010;

int e[MAXN];     // 节点值
int l[MAXN];     // 左指针（前驱）
int r[MAXN];     // 右指针（后继）
int idx;

// 初始化：使用 0 为左端点，1 为右端点（哨兵节点）
void init() {
    r[0] = 1;  // 0 的右边是 1
    l[1] = 0;  // 1 的左边是 0
    idx = 2;   // 从 2 开始分配节点
}

// 在节点 k 的右边插入值为 x 的节点
void insertRight(int k, int x) {
    e[idx] = x;
    l[idx] = k;         // 新节点的左边是 k
    r[idx] = r[k];      // 新节点的右边是 k 的右边
    l[r[k]] = idx;      // k 原右边节点的左边变成新节点
    r[k] = idx;         // k 的右边变成新节点
    idx++;
}

// 在节点 k 的左边插入值为 x 的节点
void insertLeft(int k, int x) {
    insertRight(l[k], x);  // 转化为在 k 的左边节点的右边插入
}

// 删除第 k 个节点
void remove(int k) {
    r[l[k]] = r[k];  // k 左边节点的右边指向 k 的右边
    l[r[k]] = l[k];  // k 右边节点的左边指向 k 的左边
}

5.5.3 循环链表¶

循环链表的尾节点的 next 指针指向头节点，形成一个环。它没有"末尾"的概念，从任意节点出发都能遍历整个链表，非常适合模拟围成一圈的场景。

graph LR
    A["1|→"] --> B["2|→"] --> C["3|→"] --> D["4|→"] --> E["5|→"]
    E --> A

经典例题：约瑟夫环

题意：n 个人（编号 1 ~ n）围成一圈，从 1 号开始报数，报到 m 的人出列，下一个人重新从 1 开始报数，如此反复直到所有人出列。求出列顺序。（对应题目：洛谷 P1996 约瑟夫问题）

用静态数组实现循环链表：nxt[i] 表示编号 i 的人的下一个人。删除节点只需 nxt[prev] = nxt[cur]，是 O(1) 操作。

#include <iostream>
using namespace std;

const int MAXN = 100010;

int nxt[MAXN];  // nxt[i]: 编号 i 的人的下一个人（循环链表的 next 指针）

int main() {
    int n, m;
    cin >> n >> m;  // n 个人围成一圈，报数到 m 的人出列

    // 建立循环链表：1 -> 2 -> ... -> n -> 1
    for (int i = 1; i <= n; i++) {
        nxt[i] = (i == n) ? 1 : i + 1;
    }

    int prev = n;  // cur 的前驱（删除节点时需要）
    int cur = 1;   // 从 1 号开始报数

    for (int remaining = n; remaining >= 1; remaining--) {
        // 从 cur 开始报数，报 m 下：cur 报 1，往后走 m-1 步
        for (int cnt = 1; cnt < m; cnt++) {
            prev = cur;
            cur = nxt[cur];
        }
        cout << cur << " ";        // cur 报到 m，出列
        nxt[prev] = nxt[cur];      // 从循环链表中删除 cur
        cur = nxt[prev];           // 下一轮从出列者的下一个人开始报数
    }
    cout << endl;
    return 0;
}

运行示例：

输入: 5 3
输出: 3 1 5 2 4

模拟过程：1 2 3 → 3 出列；4 5 1 → 1 出列；2 4 5 → 5 出列；2 4 2 → 2 出列；最后剩 4 出列。

时间复杂度： O(n·m)，共出列 n 次，每次报数走 m-1 步。当 m 很大时可先 m % remaining 优化。

应用场景：

约瑟夫环及其变形（如 LeetCode 1823 找出游戏的获胜者）
循环调度问题（轮流处理任务、循环缓冲区）
需要反复"绕圈"遍历并动态删除元素的模拟题

循环链表的常见坑

删除节点必须记录前驱 prev，否则无法把环重新接上（也可以用 nxt[cur] 判断"下一个"是否该删，绕过前驱，但更绕）
只剩一个节点时 nxt[cur] == cur，注意循环终止条件，避免死循环
建环时别忘了把最后一个节点接回头节点（nxt[n] = 1）

5.5.4 STL list¶

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst;

    lst.push_back(1);    // 尾部插入
    lst.push_back(2);
    lst.push_front(0);   // 头部插入

    // 遍历
    for (auto it = lst.begin(); it != lst.end(); it++) {
        cout << *it << " ";  // 输出: 0 1 2
    }
    cout << endl;

    // 在中间插入
    auto it = lst.begin();
    advance(it, 2);  // 移动到第 2 个位置
    lst.insert(it, 10);  // 在该位置前插入 10

    // 删除
    lst.erase(lst.begin());  // 删除第一个元素

    // 反转
    lst.reverse();

    // 排序
    lst.sort();

    return 0;
}

STL list 注意事项

list 不支持随机访问（不能用下标 [] 访问），查找元素需要 O(n)。在竞赛中，大多数链表题目需要用数组模拟来获得更好的性能。

5.6 哈希表¶

5.6.1 基本概念¶

哈希表（Hash Table）通过哈希函数将键映射到数组下标，实现 O(1) 的查找、插入和删除。

graph LR
    subgraph 哈希映射示意
        A["键 key"] -->|哈希函数 h| B["数组下标 idx"]
        B --> C["存储值 value"]
    end

哈希冲突： 不同的键可能映射到同一个下标，这就是哈希冲突。常见处理方法：

5.6.2 冲突处理方法一：链地址法（拉链法）¶

每个数组位置维护一个链表，映射到同一位置的元素存放在同一链表中。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100003;  // 选一个质数作为哈希表大小

int h[N];       // 哈希表，存储链表头节点下标
int e[N];       // 值
int ne[N];      // next 指针
int idx;

// 初始化哈希表
void init() {
    memset(h, -1, sizeof h);  // 所有槽位初始化为 -1（空）
    idx = 0;
}

// 将值 x 插入哈希表
void insert(int x) {
    int k = (x % N + N) % N;  // 哈希函数，取模后确保非负
    e[idx] = x;
    ne[idx] = h[k];  // 新节点指向原来链表的头部
    h[k] = idx;       // 更新链表头
    idx++;
}

// 查找值 x 是否在哈希表中
bool find(int x) {
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i]) {
        if (e[i] == x) return true;
    }
    return false;
}

5.6.3 冲突处理方法二：开放寻址法¶

当发生冲突时，按照某种探测序列寻找下一个空位。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 200003;  // 一般开 2~3 倍的大小
const int INF = 0x3f3f3f3f;  // 用一个特殊值表示空位

int h[N];  // 哈希表

// 初始化
void init() {
    memset(h, 0x3f, sizeof h);  // 全部初始化为 INF
}

// 查找值 x 的位置，如果不存在则返回应该插入的位置
int find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != INF && h[k] != x) {
        k++;           // 线性探测
        if (k == N) k = 0;  // 到达末尾，回到开头
    }
    return k;  // 返回 x 的位置或空位
}

int main() {
    init();
    int n;
    cin >> n;
    while (n--) {
        char op;
        int x;
        cin >> op >> x;
        int k = find(x);
        if (op == 'I') {
            h[k] = x;  // 插入
        } else {
            if (h[k] != INF) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    return 0;
}

5.6.4 STL unordered_map / unordered_set¶

#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int main() {
    // ===== unordered_map: 键值对映射 =====
    unordered_map<string, int> mp;

    // 插入
    mp["apple"] = 3;
    mp["banana"] = 5;
    mp.insert({"cherry", 7});

    // 查找
    cout << mp["apple"] << endl;  // 3
    cout << mp.count("banana") << endl;  // 1（存在）
    cout << mp.count("grape") << endl;   // 0（不存在）

    // 遍历
    for (auto& [key, val] : mp) {
        cout << key << ": " << val << endl;
    }

    // 删除
    mp.erase("apple");

    // ===== unordered_set: 集合 =====
    unordered_set<int> st;
    st.insert(1);
    st.insert(2);
    st.insert(3);

    cout << st.count(2) << endl;  // 1
    st.erase(2);
    cout << st.count(2) << endl;  // 0

    return 0;
}

操作	平均时间复杂度	最坏时间复杂度
插入	O(1)	O(n)
查找	O(1)	O(n)
删除	O(1)	O(n)

map vs unordered_map

map：基于红黑树，有序，O(log n) 操作
unordered_map：基于哈希表，无序，平均 O(1) 操作
竞赛中优先使用 unordered_map，但注意最坏情况可能退化到 O(n)

5.7 堆与优先队列¶

5.7.1 堆的概念¶

堆是一棵完全二叉树，满足以下性质之一：

最大堆：每个节点的值 >= 其子节点的值（堆顶是最大值）
最小堆：每个节点的值 <= 其子节点的值（堆顶是最小值）

graph TD
    subgraph 最大堆示例
        A["10 (堆顶)"] --> B["7"]
        A --> C["9"]
        B --> D["3"]
        B --> E["5"]
        C --> F["8"]
        C --> G["6"]
    end

堆通常用数组存储，对于下标为 i 的节点：

左子节点下标：2 * i + 1
右子节点下标：2 * i + 2
父节点下标：(i - 1) / 2

5.7.2 手写堆（最大堆）¶

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 100010;

int heap[MAXN];  // 用数组存储堆
int heapSize;    // 堆的当前大小

// 上浮操作：将下标为 i 的节点向上调整
void siftUp(int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;  // 父节点下标
        if (heap[parent] >= heap[i]) break;  // 已满足堆性质
        swap(heap[parent], heap[i]);  // 与父节点交换
        i = parent;  // 继续向上调整
    }
}

// 下沉操作：将下标为 i 的节点向下调整
void siftDown(int i) {
    while (2 * i + 1 < heapSize) {  // 存在子节点
        int child = 2 * i + 1;  // 左子节点
        // 如果右子节点存在且更大，选择右子节点
        if (child + 1 < heapSize && heap[child + 1] > heap[child]) {
            child++;
        }
        if (heap[i] >= heap[child]) break;  // 已满足堆性质
        swap(heap[i], heap[child]);
        i = child;
    }
}

// 插入元素 x
void insert(int x) {
    heap[heapSize] = x;
    siftUp(heapSize);
    heapSize++;
}

// 获取堆顶元素（最大值）
int top() {
    return heap[0];
}

// 删除堆顶元素
void pop() {
    heap[0] = heap[heapSize - 1];  // 将最后一个元素放到堆顶
    heapSize--;
    siftDown(0);  // 从堆顶开始下沉
}

// 建堆：对前 n 个元素建堆，时间复杂度 O(n)
void buildHeap(int n) {
    heapSize = n;
    // 从最后一个非叶子节点开始，依次向下调整
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(i);
    }
}