堆（优先队列）

堆是一种特殊的完全二叉树数据结构，在ACM竞赛中经常用于实现优先队列、解决Top-K问题以及进行堆排序等。

基本概念

【定义】堆是一种满足堆属性的完全二叉树：

• 最大堆：每个节点的值都大于或等于其子节点的值
• 最小堆：每个节点的值都小于或等于其子节点的值

【关键特性】

1. 堆是一个完全二叉树，通常使用数组实现
2. 根节点是整个堆中的最大值（最大堆）或最小值（最小堆）
3. 插入和删除操作的时间复杂度为O(log n)
4. 查找最大/最小元素的时间复杂度为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

基本操作

上浮操作 (Sift Up)

当一个节点的值大于其父节点（最大堆）或小于其父节点（最小堆）时，需要将该节点上浮：

// 最大堆的上浮操作（索引从0开始）
void siftUp(vector<int>& heap, int i) {
    int parent = (i - 1) / 2;
    while (i > 0 && heap[i] > heap[parent]) {
        swap(heap[i], heap[parent]);
        i = parent;
        parent = (i - 1) / 2;
    }
}

下沉操作 (Sift Down)

当一个节点的值小于其子节点（最大堆）或大于其子节点（最小堆）时，需要将该节点下沉：

// 最大堆的下沉操作（索引从0开始）
void siftDown(vector<int>& heap, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // 找出当前节点和其子节点中的最大值
    if (left < n && heap[left] > heap[largest]) {
        largest = left;
    }
    if (right < n && heap[right] > heap[largest]) {
        largest = right;
    }

    // 如果最大值不是当前节点，则交换并继续下沉
    if (largest != i) {
        swap(heap[i], heap[largest]);
        siftDown(heap, n, largest);
    }
}

插入操作

将新元素添加到堆的末尾，然后执行上浮操作：

void insert(vector<int>& heap, int val) {
    // 将新元素添加到末尾
    heap.push_back(val);

    // 执行上浮操作
    siftUp(heap, heap.size() - 1);
}

删除最大/最小元素

将根节点与最后一个节点交换，移除最后一个节点，然后对新的根节点执行下沉操作：

int extractMax(vector<int>& heap) {
    if (heap.empty()) {
        throw runtime_error("Heap is empty");
    }

    int maxVal = heap[0];  // 保存最大值

    // 将最后一个元素放到根节点，并缩小堆
    heap[0] = heap.back();
    heap.pop_back();

    // 如果堆不为空，对新的根节点执行下沉操作
    if (!heap.empty()) {
        siftDown(heap, heap.size(), 0);
    }

    return maxVal;
}

堆的构建

从无序数组构建堆的方式有两种：

1. 逐个插入（时间复杂度O(n log n)）

vector<int> buildHeap(const vector<int>& arr) {
    vector<int> heap;
    for (int val : arr) {
        insert(heap, val);
    }
    return heap;
}

2. 原地建堆（时间复杂度O(n)）

从最后一个非叶节点开始，依次向前执行下沉操作：

// 原地建堆，时间复杂度O(n)
void buildHeap(vector<int>& arr) {
    int n = arr.size();

    // 从最后一个非叶节点开始，依次向前执行下沉操作
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, n, i);
    }
}

堆排序

堆排序是一种基于比较的排序算法，它利用堆的性质进行排序：

void heapSort(vector<int>& arr) {
    int n = arr.size();

    // 构建最大堆
    buildHeap(arr);

    // 一个个取出堆顶元素
    for (int i = n - 1; i > 0; i--) {
        // 将堆顶元素（当前最大值）与数组末尾交换
        swap(arr[0], arr[i]);

        // 对剩余元素进行下沉操作，重新构建最大堆
        siftDown(arr, i, 0);
    }
}

堆排序的时间复杂度为O(n log n)，空间复杂度为O(1)，是一种原地排序算法。

STL中的优先队列

C++标准库提供了优先队列容器priority_queue，它是基于堆实现的：

#include <queue>
#include <vector>
using namespace std;

// 最大堆（默认）
priority_queue<int> maxHeap;

// 最小堆
priority_queue<int, vector<int>, greater<int>> minHeap;

// 自定义比较函数
struct compare {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a.first < b.first;  // 按first降序排列
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> customHeap;

基本操作

// 插入元素
maxHeap.push(10);

// 访问堆顶元素
int top = maxHeap.top();

// 移除堆顶元素
maxHeap.pop();

// 获取堆的大小
int size = maxHeap.size();

// 判断堆是否为空
bool isEmpty = maxHeap.empty();

堆的应用

1. Top-K问题

在n个元素中找出最大/最小的k个元素：

// 找出数组中最大的k个元素
vector<int> findTopK(const vector<int>& nums, int k) {
    // 使用最小堆
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // 只保留k个最大元素
    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();  // 弹出最小的元素
        }
    }

    // 将结果转换为数组
    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }

    // 按升序排序结果
    reverse(result.begin(), result.end());
    return result;
}

2. 堆优化的Dijkstra算法

使用堆（优先队列）可以优化Dijkstra算法，将时间复杂度从O(V²)降低到O(E log V)：

// 堆优化的Dijkstra算法（参见图论算法章节）
void dijkstra(vector<vector<pair<int, int>>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;

    // {距离, 顶点} 的优先队列（最小堆）
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;  // 跳过已经处理过的节点

        for (auto [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

3. 中位数维护

使用一个最大堆和一个最小堆可以高效地维护数据流的中位数：

class MedianFinder {
private:
    priority_queue<int> maxHeap;  // 存储较小的一半元素
    priority_queue<int, vector<int>, greater<int>> minHeap;  // 存储较大的一半元素

public:
    void addNum(int num) {
        // 始终保持 maxHeap.size() >= minHeap.size()
        if (maxHeap.empty() || num <= maxHeap.top()) {
            maxHeap.push(num);
        } else {
            minHeap.push(num);
        }

        // 调整两个堆的大小，使它们的大小差不超过1
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        } else if (maxHeap.size() < minHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }

    double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.top();
        } else {
            return (maxHeap.top() + minHeap.top()) / 2.0;
        }
    }
};

4. 合并K个有序链表/数组

使用最小堆可以高效地合并多个有序数据结构：

ListNode* mergeKLists(vector<ListNode*>& lists) {
    // 自定义比较函数
    auto compare = [](ListNode* a, ListNode* b) {
        return a->val > b->val;  // 最小堆
    };

    // 创建最小堆
    priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> minHeap(compare);

    // 将每个链表的头节点加入堆
    for (ListNode* list : lists) {
        if (list) minHeap.push(list);
    }

    // 哨兵节点
    ListNode dummy(0);
    ListNode* tail = &dummy;

    // 依次取出堆顶元素，并将下一个节点加入堆
    while (!minHeap.empty()) {
        ListNode* curr = minHeap.top();
        minHeap.pop();

        tail->next = curr;
        tail = tail->next;

        if (curr->next) {
            minHeap.push(curr->next);
        }
    }

    return dummy.next;
}

相关变种和扩展

1. 索引堆

索引堆维护元素的索引而非元素本身，适用于需要随机访问堆中元素的场景：

class IndexMinHeap {
private:
    vector<int> data;    // 原始数据
    vector<int> indexes; // 索引数组，indexes[i]表示堆中第i个位置存储的元素在data中的索引
    vector<int> reverse; // 反向索引，reverse[i]表示索引i在indexes中的位置，如果不在堆中则为-1

    // 比较函数
    bool less(int i, int j) {
        return data[indexes[i]] < data[indexes[j]];
    }

    // 交换indexes[i]和indexes[j]
    void swap(int i, int j) {
        std::swap(indexes[i], indexes[j]);
        reverse[indexes[i]] = i;
        reverse[indexes[j]] = j;
    }

    // 上浮操作
    void siftUp(int k) {
        while (k > 0) {
            int parent = (k - 1) / 2;
            if (!less(k, parent)) break;
            swap(k, parent);
            k = parent;
        }
    }

    // 下沉操作
    void siftDown(int k) {
        int n = indexes.size();
        while (2 * k + 1 < n) {
            int j = 2 * k + 1; // 左子节点
            if (j + 1 < n && less(j + 1, j)) j++; // 取两个子节点中较小者
            if (!less(j, k)) break;
            swap(k, j);
            k = j;
        }
    }

public:
    IndexMinHeap(int capacity) {
        data.resize(capacity);
        indexes.clear();
        reverse.resize(capacity, -1);
    }

    int size() {
        return indexes.size();
    }

    bool isEmpty() {
        return indexes.empty();
    }

    // 插入元素
    void insert(int i, int val) {
        data[i] = val;
        indexes.push_back(i);
        reverse[i] = indexes.size() - 1;
        siftUp(indexes.size() - 1);
    }

    // 弹出最小元素
    int extractMin() {
        int minIndex = indexes[0];
        swap(0, indexes.size() - 1);
        reverse[indexes.back()] = -1;
        indexes.pop_back();
        siftDown(0);

        return minIndex;
    }

    // 更新元素值
    void update(int i, int val) {
        data[i] = val;
        siftUp(reverse[i]);
        siftDown(reverse[i]);
    }

    // 判断索引i是否在堆中
    bool contains(int i) {
        return reverse[i] != -1;
    }

    // 获取最小元素的索引
    int getMinIndex() {
        return indexes[0];
    }

    // 获取最小元素的值
    int getMinValue() {
        return data[indexes[0]];
    }
};

2. 二项堆和斐波那契堆

这些是更高级的堆结构，支持更多高效的操作，例如合并两个堆和减小键值。

堆的常见面试题和竞赛题

1. 合并K个有序数组/链表：使用堆来高效地合并
2. 第K大/小元素：使用堆来维护前K大/小的元素
3. 滑动窗口最大/最小值：使用堆来跟踪窗口内的最大/最小值
4. 任务调度：使用堆来选择优先级最高的任务
5. 丑数：使用堆来生成按顺序的丑数
6. K近邻算法：使用堆来找到最近的K个点
7. 流量控制：在网络流量监控中维护高流量连接
8. 多路归并：合并多个有序数据源时的选择策略

堆的实际应用

1. 优先级队列：操作系统中的任务调度
2. 图算法：Dijkstra、Prim等算法的优化
3. 事件驱动模拟：离散事件模拟
4. 数据流处理：维护数据流中的统计信息，如中位数、Top-K等
5. 定时任务管理：操作系统中的定时器实现
6. 带宽管理：网络路由器中的数据包优先级处理
7. 内存管理：某些垃圾回收算法中的引用计数管理
8. 游戏开发：寻路算法的开销优化、决策树剪枝

堆的性能分析与比较

时间复杂度

*斐波那契堆的摊销时间复杂度

空间复杂度

• 数组实现：O(n)，紧凑但需要连续内存
• 链表实现：O(n)，但有额外指针开销
• 斐波那契堆：O(n)，但常数因子较大

优缺点比较

数组实现

• 优点：内存紧凑，缓存友好，实现简单
• 缺点：合并操作不高效，需要连续内存

STL priority_queue

• 优点：标准库实现，稳定可靠，使用方便
• 缺点：功能有限，不支持修改键值和迭代

二项堆/斐波那契堆

• 优点：某些操作的理论复杂度更优，支持高效合并
• 缺点：实现复杂，常数因子大，实际性能可能不如简单堆

技巧与总结

1. 对于需要频繁获取最大/最小值的场景，优先考虑使用堆
2. 对于Top-K问题，使用大小为K的堆可以高效解决
3. STL中的priority_queue已经提供了完整的堆实现，无需自行编写
4. 使用自定义比较函数可以灵活地改变堆的排序方式
5. 索引堆是处理需要随机访问和修改堆元素的有力工具
6. 在图算法中，堆常用于优化最短路径和最小生成树算法
7. 当需要频繁修改和合并堆时，考虑使用更高级的堆结构
8. 在多线程环境中使用堆时，需要考虑并发安全问题

常见错误与陷阱

1. 忘记更新堆属性：修改堆中元素后未执行上浮或下沉操作
2. 比较函数设置错误：导致创建了最小堆而期望最大堆，或反之
3. 堆空检查：在执行弹出操作前未检查堆是否为空
4. 自定义类型缺少比较运算符：使用自定义类型时未提供比较方法
5. 误解STL容器行为：priority_queue默认是最大堆，而非最小堆
6. 重复索引问题：在索引堆中误用了相同的索引值
7. 线程安全问题：在并发环境中未对堆操作进行适当的同步

练习题推荐

1. LeetCode 215: 数组中的第K个最大元素
2. LeetCode 23: 合并K个升序链表
3. LeetCode 347: 前K个高频元素
4. LeetCode 295: 数据流的中位数
5. LeetCode 239: 滑动窗口最大值
6. LeetCode 973: 最接近原点的K个点
7. LeetCode 1046: 最后一块石头的重量
8. LeetCode 703: 数据流中的第K大元素
9. LeetCode 1642: 可以到达的最远建筑
10. LeetCode 1834: 单线程CPU
11. POJ 3253: Fence Repair（使用哈夫曼编码思想）
12. POJ 2431: Expedition（贪心+优先队列）
13. Codeforces 903C: Boxes Packing（使用优先队列的贪心策略）
14. SPOJ RMID2: Running Median（双堆维护中位数）
15. UVA 11995: I Can Guess the Data Structure!（判断数据结构类型）