大根堆建立并输出的c++代码

大根堆（Max Heap），是一种特殊的树形数据结构，其父节点的值总是大于或等于其所有子节点的值。在C++中，我们可以使用数组来实现一个大根堆，因为数组有固定的索引方便操作。以下是创建大根堆并支持插入元素和输出最大元素的基本代码：

#include <iostream>
using namespace std;

// 定义堆的最大大小
#define MAX_SIZE 100

// 大根堆结构体，包含一个数组存储堆的数据，以及当前堆的大小
struct MaxHeap {
    int heap[MAX_SIZE];
    int size;
};

// 插入元素到堆中，保证满足大根堆性质
void insert(MaxHeap& h, int value) {
    if (h.size == MAX_SIZE)
        throw "Heap is full!";

    h.heap[h.size] = value; // 将新元素添加到末尾
    int i = h.size - 1; // 初始位置为最后一个元素

    while (i > 0 && h.heap[i] > h.heap[(i - 1) / 2]) { // 当前元素大于其父节点，就交换位置并调整
        swap(h.heap[i], h.heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
    h.size++;
}

// 输出最大元素
int extractMax(MaxHeap& h) {
    if (h.size <= 0)
        throw "Heap is empty!";

    int max_value = h.heap[0]; // 存储最大元素
    h.heap[0] = h.heap[h.size - 1]; // 将最后一个元素放到根部
    h.size--;

    // 调整堆，保持大根堆性质
    for (int i = 0; i <= h.size / 2; i++) {
        swap(h.heap[i], h.heap[h.size - (i + 1)]);
        while (h.heap[i] > h.heap[(i * 2) + 1]) { // 如果父节点小于左孩子，就与左孩子交换并继续调整
            swap(h.heap[i], h.heap[(i * 2) + 1]);
            i = (i * 2) + 1;
        }
    }

    return max_value;
}

int main() {
    MaxHeap h;
    h.size = 0;

    // 插入一些元素示例
    h.insert(h, 9);
    h.insert(h, 5);
    h.insert(h, 18);
    h.insert(h, 2);

    cout << "Max element in the heap: " << h.extractMax(h) << endl;

    // 输出堆顶元素直到堆为空
    for (int i = 0; i < h.size; ++i) {
        cout << "Element at index " << i << ": " << h.heap[i] << endl;
    }

    return 0;
}

这段代码首先定义了一个`MaxHeap`结构体，包含了大根堆的数组`heap`、当前堆大小`size`。`insert`函数用于向堆中插入元素，`extractMax`函数用于移除并返回堆顶最大的元素，并通过调整保持堆的特性。在`main`函数里，我们演示了如何创建并操作一个大根堆。