C++怎么实现一个大根堆和小根堆_C++数据结构与堆排序应用

答案：C++中可通过priority_queue或手动实现数组堆来构建大根堆和小根堆。1. priority_queue默认为大根堆，小根堆需使用greater；2. 手动实现时，大根堆通过父节点大于子节点的性质，用shiftUp和shiftDown维护结构，小根堆反之。两种方式均适用于堆排序等场景。

在C++中实现大根堆和小根堆，可以借助标准库中的 priority_queue，也可以手动实现基于数组的堆结构。下面从两种方式出发，介绍如何构建大根堆和小根堆，并结合堆排序的应用说明其使用场景。

使用 priority_queue 实现大根堆和小根堆

C++ 标准库中的 priority_queue 默认是一个大根堆，可以直接使用。若要实现小根堆，需要指定比较函数。

示例代码：

#include <queue>
#include <vector>
#include <iostream>
<p>// 大根堆（默认）
std::priority_queue<int> max_heap;</p><p>// 小根堆（使用 greater）
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;</p><p>// 使用示例
max_heap.push(10);
max_heap.push(30);
max_heap.push(20);</p><p>std::cout << "大根堆顶部: " << max_heap.top() << std::endl; // 输出 30</p><p><span>立即学习</span>“<a href="https://pan.quark.cn/s/6e7abc4abb9f" style="text-decoration: underline !important; color: blue; font-weight: bolder;" rel="nofollow" target="_blank">C++免费学习笔记（深入）</a>”；</p><p>min_heap.push(10);
min_heap.push(30);
min_heap.push(20);</p><p>std::cout << "小根堆顶部: " << min_heap.top() << std::endl; // 输出 10</p>

手动实现堆结构（数组 + 下标操作）

堆本质是一棵完全二叉树，可用数组表示。父节点与子节点的下标关系如下：

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

通过 上浮（shift up） 和 下沉（shift down） 操作维护堆性质。

class MaxHeap {
private:
    std::vector<int> heap;
<pre class='brush:php;toolbar:false;'>void shiftUp(int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] <= heap[parent]) break;
        std::swap(heap[i], heap[parent]);
        i = parent;
    }
}

void shiftDown(int i) {
    int n = heap.size();
    while (true) {
        int maxIndex = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && heap[left] > heap[maxIndex])
            maxIndex = left;
        if (right < n && heap[right] > heap[maxIndex])
            maxIndex = right;

        if (maxIndex == i) break;
        std::swap(heap[i], heap[maxIndex]);
        i = maxIndex;
    }
}

登录后复制

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

void pop() {
    if (heap.empty()) return;
    std::swap(heap[0], heap.back());
    heap.pop_back();
    shiftDown(0);
}

int top() { return heap.empty() ? -1 : heap[0]; }
bool empty() { return heap.empty(); }

登录后复制

};

标签： c++ 大根堆小根堆 ios stream 标准库