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

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

穿越時空

发布： 2025-12-17 18:18:44

原创

792人浏览过

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

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

在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(); }

登录后复制

};

ListenLeap

AI辅助通过播客学英语

217

查看详情

小根堆只需将比较条件反过来即可（如 > 改为

堆排序的基本原理与实现

堆排序利用大根堆的性质，每次将堆顶最大元素移到末尾，然后调整剩余元素为新堆。

步骤：

构建大根堆（从最后一个非叶子节点开始下沉）
交换堆顶与堆尾元素
缩小堆大小，对新堆顶执行下沉
重复直到堆只剩一个元素

void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
<pre class='brush:php;toolbar:false;'>if (left < n && arr[left] > arr[largest])
    largest = left;
if (right < n && arr[right] > arr[largest])
    largest = right;

if (largest != i) {
    std::swap(arr[i], arr[largest]);
    heapify(arr, n, largest);
}

登录后复制

}

void heapSort(std::vector& arr) { int n = arr.size();

// 构建大根堆
for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);

// 堆排序
for (int i = n - 1; i > 0; i--) {
    std::swap(arr[0], arr[i]);
    heapify(arr, i, 0); // 排除已排序部分
}

登录后复制

}

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

基本上就这些。标准库优先队列适合快速开发，手动实现有助于理解底层机制，堆排序在内存受限或需保证最坏情况性能时很有用。

以上就是C++怎么实现一个大根堆和小根堆_C++数据结构与堆排序应用的详细内容，更多请关注php中文网其它相关文章！