欢迎来到雄杰鑫电商资讯网
技术教程

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

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

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

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

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

示例代码：

#include 
#include 
#include 

// 大根堆（默认）
std::priority_queue max_heap;
// 小根堆（使用 greater）
std::priority_queue, std::greater> min_heap;
// 使用示例
max_heap.push(10);
max_heap.push(30);
max_heap.push(20);
std::cout << "大根堆顶部: " << max_heap.top() << std::endl; // 输出 30
min_heap.push(10);
min_heap.push(30);
min_heap.push(20);
std::cout << "小根堆顶部: " << min_heap.top() << std::endl; // 输出 10

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

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

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

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

class MaxHeap {
private:
    std::vector heap;

void shiftUp(int i) {
    while (i youjiankuohaophpcn 0) {
        int parent = (i - 1) / 2;
        if (heap[i] zuojiankuohaophpcn= 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 zuojiankuohaophpcn n && heap[left] youjiankuohaophpcn heap[maxIndex])
            maxIndex = left;
        if (right zuojiankuohaophpcn n && heap[right] youjiankuohaophpcn 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(); }
};


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


堆排序的基本原理与实现


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


步骤：


    

  • 构建大根堆（从最后一个非叶子节点开始下沉）
    • 

  • 交换堆顶与堆尾元素
    • 

  • 缩小堆大小，对新堆顶执行下沉
    • 

  • 重复直到堆只剩一个元素
    • 



void heapify(std::vector& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

if (left zuojiankuohaophpcn n && arr[left] youjiankuohaophpcn arr[largest])
    largest = left;
if (right zuojiankuohaophpcn n && arr[right] youjiankuohaophpcn 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 youjiankuohaophpcn= 0; i--)
    heapify(arr, n, i);

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


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


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






            
 数据结构 是一个 是一种 适用于 只需 可通过 不稳定 两种 stream ios 堆 public c++ 库中 标准库 可以直接 int void 一棵

相关文章

按ESC键退出。