数据结构：堆（Heap）

验证映射关系：i=1 的父节点是 (1-1)/2=0，i=2 的左子节点是 2*2+1=5，完全符合数组存储逻辑。

三、堆的核心操作（C++ 模板实现）

堆的所有功能基于两个核心操作：上浮（Sift Up） 和 下沉（Sift Down）。下面实现一个支持大根堆/小根堆的通用模板类 Heap<T, Compare>，其中 Compare 是比较函数对象（默认大根堆）。

3.1 模板类框架

#include <vector>
#include <algorithm>
#include <stdexcept>

// 比较函数对象：大根堆（默认）
template<typename T>
struct MaxHeapCompare {
    bool operator()(const T& a, const T& b) const {
        return a < b; // 父节点需大于子节点，故 a<b 时需交换
    }
};

// 比较函数对象：小根堆
template<typename T>
struct MinHeapCompare {
    bool operator()(const T& a, const T& b) const {
        return a > b; // 父节点需小于子节点，故 a>b 时需交换
    }
};

// 堆模板类：T 为元素类型，Compare 为比较规则
template<typename T, typename Compare = MaxHeapCompare<T>>
class Heap {
private:
    std::vector<T> data; // 存储堆的数组
    Compare cmp;         // 比较函数对象

    // 上浮操作：从索引 i 向上调整堆
    void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (!cmp(data[parent], data[i])) break;
            std::swap(data[parent], data[i]);
            i = parent;
        }
    }

    // 下沉操作：从索引 i 向下调整堆
    void siftDown(int i) {
        int n = data.size();
        while (true) {
            int maxChild = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < n && cmp(data[maxChild], data[left])) maxChild = left;
            if (right < n && cmp(data[maxChild], data[right])) maxChild = right;

            if (maxChild == i) break;
            std::swap(data[i], data[maxChild]);
            i = maxChild;
        }
    }

public:
    Heap() = default;

    Heap(const std::vector<T>& arr) : data(arr) {
        buildHeap();
    }

    void buildHeap() {
        int n = data.size();
        int lastNonLeaf = (n - 2) / 2;
        for (int i = lastNonLeaf; i >= 0; --i) {
            siftDown(i);
        }
    }

    void push(const T& val) {
        data.push_back(val);
        siftUp(data.size() - 1);
    }

    void pop() {
        if (empty()) throw std::runtime_error("Heap is empty, cannot pop!");
        int n = data.size();
        data[0] = data[n - 1];
        data.pop_back();
        if (!empty()) siftDown(0);
    }

    const T& top() const {
        if (empty()) throw std::runtime_error("Heap is empty, cannot get top!");
        return data[0];
    }

    bool empty() const { return data.empty(); }
    size_t size() const { return data.size(); }
};

3.2 核心操作详解

3.2.1 上浮（siftUp）

• 场景：插入新元素后，堆序可能被破坏。
• 原理：从新元素的位置向上遍历，与父节点比较，若不满足堆序则交换，直到到达根节点或满足堆序。
• 时间复杂度：O(logn)。

3.2.2 下沉（siftDown）

• 场景：删除堆顶后，堆序被破坏。
• 原理：从堆顶开始，与左右子节点中'符合堆序的极值节点'比较，若不满足堆序则交换。
• 关键细节：需先判断左右子节点是否存在（避免数组越界）。
• 时间复杂度：O(logn)。

3.2.3 建堆（buildHeap）

• 自底向上法：从最后一个非叶子节点开始，逐个执行下沉操作，时间复杂度 O(n)。
• 代码逻辑：最后一个非叶子节点索引为 (n-2)/2，从该节点向左遍历至根，依次执行 siftDown。

四、堆的经典应用

4.1 堆排序（原地排序）

堆排序利用大根堆（升序）或小根堆（降序）实现排序，时间复杂度 O(nlogn)，空间复杂度 O(1)，但不稳定。

C++ 实现：

template<typename T>
void heapSort(std::vector<T>& arr) {
    int n = arr.size();
    if (n <= 1) return;

    auto buildMaxHeap = [&](std::vector<T>& a, int size) {
        int lastNonLeaf = (size - 2) / 2;
        for (int i = lastNonLeaf; i >= 0; --i) {
            int parent = i;
            while (true) {
                int maxChild = parent;
                int left = 2 * parent + 1;
                int right = 2 * parent + 2;
                if (left < size && a[left] > a[maxChild]) maxChild = left;
                if (right < size && a[right] > a[maxChild]) maxChild = right;
                if (maxChild == parent) break;
                std::swap(a[parent], a[maxChild]);
                parent = maxChild;
            }
        }
    };

    buildMaxHeap(arr, n);
    for (int i = n - 1; i > 0; --i) {
        std::swap(arr[0], arr[i]);
        buildMaxHeap(arr, i);
    }
}

4.2 优先队列（Priority Queue）

优先队列是堆的典型应用，元素按优先级排序。C++ STL 提供 priority_queue，底层基于堆实现。

改为小根堆的两种方式：

1. 使用 greater<T>（需包含 <functional>）；
2. 自定义比较函数对象。

示例：任务调度

#include <queue>
#include <functional>
#include <iostream>
#include <string>

struct Task {
    std::string name;
    int priority;
    Task(std::string n, int p) : name(n), priority(p) {}
};

struct TaskCompare {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority > b.priority;
    }
};

int main() {
    std::priority_queue<Task> maxPq;
    maxPq.push(Task("任务 A", 3));
    maxPq.push(Task("任务 B", 5));
    maxPq.push(Task("任务 C", 2));

    while (!maxPq.empty()) {
        auto task = maxPq.top();
        maxPq.pop();
        std::cout << "执行：" << task.name << "（优先级：" << task.priority << ")" << std::endl;
    }
    return 0;
}

4.3 TopK 问题（海量数据前 K 大元素）

使用小根堆可实现 O(nlogK) 时间复杂度、O(K) 空间复杂度。

C++ 实现：

#include <vector>
#include <queue>
#include <iostream>

std::vector<int> topK(std::vector<int>& data, int k) {
    if (data.empty() || k <= 0 || k > data.size()) throw std::invalid_argument("Invalid input!");

    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    for (int i = 0; i < k; ++i) minHeap.push(data[i]);

    for (int i = k; i < data.size(); ++i) {
        if (data[i] > minHeap.top()) {
            minHeap.pop();
            minHeap.push(data[i]);
        }
    }

    std::vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    return result;
}

4.4 中位数问题（动态数据实时获取中位数）

使用两个堆（大根堆 + 小根堆）可实现 O(logn) 插入和 O(1) 查询。

C++ 实现：

#include <vector>
#include <queue>
#include <iostream>
#include <stdexcept>

class MedianFinder {
private:
    std::priority_queue<int> leftHeap; // 大根堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> rightHeap; // 小根堆

    void balance() {
        if (leftHeap.size() - rightHeap.size() == 2) {
            rightHeap.push(leftHeap.top());
            leftHeap.pop();
        } else if (rightHeap.size() - leftHeap.size() == 1) {
            leftHeap.push(rightHeap.top());
            rightHeap.pop();
        }
    }

public:
    MedianFinder() = default;

    void addNum(int num) {
        if (leftHeap.empty() || num <= leftHeap.top()) {
            leftHeap.push(num);
        } else {
            rightHeap.push(num);
        }
        balance();
    }

    double findMedian() {
        if (leftHeap.empty() && rightHeap.empty()) throw std::runtime_error("No data!");
        if (leftHeap.size() > rightHeap.size()) return leftHeap.top();
        return (leftHeap.top() + rightHeap.top()) / 2.0;
    }
};

五、堆的优缺点与适用场景

5.1 优点

• 极值查询（堆顶）：O(1) 常数时间；
• 插入/删除堆顶：O(logn) 高效；
• 存储紧凑：数组存储，无额外指针开销；
• 支持动态数据。

5.2 缺点

• 随机访问低效：O(n)；
• 查找任意元素低效：O(n)；
• 堆排序不稳定；
• 调整堆开销。

5.3 适用场景

• 优先队列；
• 排序（堆排序）；
• TopK 问题；
• 中位数查询；
• 贪心算法。

六、常见误区与注意事项

1. 建堆时间复杂度：自底向上建堆是 O(n)，而非 O(nlogn)；
2. STL priority_queue 的坑：pop() 不返回元素，需先 top() 再 pop()；
3. 下沉操作的边界：必须判断左右子节点是否存在；
4. 堆与 BST 的区别：堆是'父子有序，全局无序'，BST 是'左小右大，全局有序'；
5. TopK 问题的堆选择：前 K 大用小根堆，前 K 小用大根堆。

补充建堆的 O(n) 复杂度推导

求和式 $\sum_{k=0}^{h-1} 2^k \times (h - k)$ 是典型的「等差×等比」数列求和，适合用错位相减法求解。

第一步：计算求和式的精确值

设 $S = \sum_{k=0}^{h-1} 2^k \times (h - k)$，展开得： $S = h \times 2^0 + (h-1) \times 2^1 + \dots + 1 \times 2^{h-1}$

两边乘以 2： $2S = h \times 2^1 + (h-1) \times 2^2 + \dots + 1 \times 2^h$

相减得： $S = 2^{h+1} - h - 2$

第二步：建立 h 与 n 的关系

对于满二叉树，节点数 $n = 2^h - 1$，故 $2^h = n + 1$，$2^{h+1} = 2n + 2$。

第三步：推导 S = O(n)

代入得 $S = (2n + 2) - h - 2 = 2n - h$。

因为 $h = \log_2(n+1) \approx \log_2 n$，相对于 $n$ 为低阶项，主导项为 $2n$。

因此，$S = O(n)$。

堆是基于完全二叉树的高效数据结构，核心优势在于 O(1) 极值查询和 O(logn) 插入/删除。掌握堆的关键在于理解'上浮'和'下沉'的维护逻辑，以及建堆的 O(n) 复杂度推导。在实际开发中，优先使用 STL 的 priority_queue，但自定义堆实现能更深入理解其底层原理。