算法入门——堆（C++）详解：从理论到实现

堆是一种高效的数据结构，广泛应用于优先队列、堆排序、图算法等领域。本文将带你深入理解堆的原理与实现，掌握C++中堆的应用技巧。

一、什么是堆？

堆（Heap）是一种特殊的完全二叉树数据结构，满足以下性质：

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

• 完全二叉树：除了最后一层，其他层节点都是满的，且最后一层节点从左向右排列

堆的两种类型：

1. 最大堆（大顶堆）：父节点值 ≥ 子节点值

2. 最小堆（小顶堆）：父节点值 ≤ 子节点值

二、堆的存储：数组表示法

堆通常使用数组存储，利用完全二叉树的性质：

• 对于索引

  • 父节点索引：(i-1)/2

  • 左子节点索引：2*i + 1

  • 右子节点索引：2*i + 2

三、堆的核心操作

1. 上浮（Shift Up）操作

当在堆尾添加新元素后，需要向上调整以维持堆序性

// 最大堆的上浮操作
void shiftUp(vector<int>& heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[parent] >= heap[index]) break;
        swap(heap[parent], heap[index]);
        index = parent;
    }
}

2. 下沉（Shift Down）操作

当移除堆顶元素后，需要将堆尾元素移到堆顶，并向下调整

// 最大堆的下沉操作
void shiftDown(vector<int>& heap, int size, int index) {
    int left = 2 * index + 1;
    while (left < size) {
        int right = left + 1;
        int larger = (right < size && heap[right] > heap[left]) ? right : left;
        
        if (heap[index] >= heap[larger]) break;
        
        swap(heap[index], heap[larger]);
        index = larger;
        left = 2 * index + 1;
    }
}

3. 建堆操作（Heapify）

将无序数组构建成堆的两种方法：

• 自底向上法：O(n)时间复杂度

• 自顶向下法：O(nlogn)时间复杂度

// 高效建堆：自底向上法
void buildHeap(vector<int>& arr) {
    int n = arr.size();
    // 从最后一个非叶子节点开始下沉
    for (int i = (n - 2) / 2; i >= 0; i--) {
        shiftDown(arr, n, i);
    }
}

四、堆的操作接口实现

class MaxHeap {
private:
    vector<int> heap;
    
    void shiftUp(int index) {
        /* 上浮实现 */
    }
    
    void shiftDown(int index, int size) {
        /* 下沉实现 */
    }
    
public:
    // 插入元素
    void push(int val) {
        heap.push_back(val);
        shiftUp(heap.size() - 1);
    }
    
    // 移除堆顶元素
    void pop() {
        if (heap.empty()) return;
        heap[0] = heap.back();
        heap.pop_back();
        shiftDown(0, heap.size());
    }
    
    // 获取堆顶元素
    int top() {
        if (heap.empty()) return -1; // 错误处理
        return heap[0];
    }
    
    // 堆大小
    int size() {
        return heap.size();
    }
    
    // 打印堆
    void print() {
        for (int num : heap) {
            cout << num << " ";
        }
        cout << endl;
    }
};

五、C++ STL中的堆：priority_queue

C++标准库提供了优先队列容器，底层使用堆实现：

#include <queue>
#include <iostream>

using namespace std;

int main() {
    // 最大堆（默认）
    priority_queue<int> maxHeap;
    
    // 最小堆
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    // 操作示例
    maxHeap.push(3);
    maxHeap.push(1);
    maxHeap.push(4);
    maxHeap.push(2);
    
    cout << "Max Heap: ";
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    // 输出：4 3 2 1
    
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(2);
    
    cout << "\nMin Heap: ";
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    // 输出：1 2 3 4
    
    return 0;
}

六、堆的应用场景

1. 堆排序（Heap Sort）

时间复杂度：O(nlogn)，空间复杂度：O(1)

void heapSort(vector<int>& arr) {
    // 构建最大堆
    buildHeap(arr);
    
    // 逐步提取最大值
    for (int i = arr.size() - 1; i > 0; i--) {
        swap(arr[0], arr[i]);    // 将最大值移到末尾
        shiftDown(arr, i, 0);    // 调整剩余元素
    }
}

2. Top K问题

查找数组中最大/最小的K个元素

vector<int> topK(vector<int>& nums, int k) {
    // 最小堆用于保存最大的k个元素
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    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();
    }
    return result;
}

3. 合并K个有序链表

使用最小堆高效合并多个有序序列

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* mergeKLists(vector<ListNode*>& lists) {

    auto cmp = [ ](ListNode* a, ListNode* b) {

        return a->val > b->val; // 最小堆
    };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
    
    for (ListNode* node : lists) {
        if (node) pq.push(node);
    }
    
    ListNode dummy(0);
    ListNode* tail = &dummy;
    
    while (!pq.empty()) {
        ListNode* node = pq.top();
        pq.pop();
        tail->next = node;
        tail = tail->next;
        if (node->next) pq.push(node->next);
    }
    
    return dummy.next;
}

七、堆的复杂度分析

八、总结与练习

堆是一种高效的数据结构，特别适合需要频繁访问最大/最小元素的场景。通过本文，你应该掌握：

1. 堆的基本概念和性质

2. 堆的核心操作：上浮、下沉、建堆

3. C++中堆的实现与STL应用

4. 堆的经典应用场景

练习题：

1. 实现一个最小堆类，支持插入、删除、获取最小值操作

2. 使用堆实现一个实时数据流的中位数查找器

3. 解决LeetCode 347：前K个高频元素

堆是算法学习中的核心数据结构，深入理解其原理和实现，将为学习更高级算法打下坚实基础！

// 完整堆实现示例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class MaxHeap {
private:
    vector<int> data;

    void shiftUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (data[parent] >= data[index]) break;
            swap(data[parent], data[index]);
            index = parent;
        }
    }

    void shiftDown(int index) {
        int size = data.size();
        int left = 2 * index + 1;
        while (left < size) {
            int right = left + 1;
            int larger = left;
            if (right < size && data[right] > data[left]) {
                larger = right;
            }
            if (data[index] >= data[larger]) break;
            swap(data[index], data[larger]);
            index = larger;
            left = 2 * index + 1;
        }
    }

public:
    void push(int val) {
        data.push_back(val);
        shiftUp(data.size() - 1);
    }

    void pop() {
        if (data.empty()) return;
        data[0] = data.back();
        data.pop_back();
        if (!data.empty()) shiftDown(0);
    }

    int top() {
        if (data.empty()) throw out_of_range("Heap is empty");
        return data[0];
    }

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

    bool empty() {
        return data.empty();
    }

    void print() {
        for (int num : data) cout << num << " ";
        cout << endl;
    }
};

int main() {
    MaxHeap heap;
    heap.push(3);
    heap.push(1);
    heap.push(4);
    heap.push(9);
    heap.push(5);
    heap.push(2);
    
    cout << "Max Heap: ";
    while (!heap.empty()) {
        cout << heap.top() << " ";
        heap.pop();
    }
    // 输出：9 5 4 3 2 1
    
    return 0;
}

希望这篇教程能帮助你全面理解堆这一重要数据结构！在实际应用中，根据需求选择使用STL的priority_queue或自定义堆实现。