c语言代码实现一个大根堆,即根节点为所有元素最大值的堆,需要支持插入元素、查询堆顶元素、删除堆顶元素三个操作。
时间: 2024-09-26 07:03:43 浏览: 38
STL_quene.rar_crowd7oc_优先队列 堆_大根堆_大根对 c++_小根堆
在C语言中,我们可以使用数组来实现大根堆(Max Heap)。一个大根堆是一个完全二叉树,其中每个节点的值都大于或等于其子节点的值。以下是大根堆的基本操作实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_HEAP_SIZE 100 // 设置堆的最大容量
#define LEFT_CHILD(i) (2*i + 1)
#define RIGHT_CHILD(i) (2*i + 2)
#define PARENT(i) (i / 2)
typedef struct Node {
int data; // 节点的数据
int index; // 节点在数组中的位置
} Node;
// 初始化堆
void initHeap(Node heap[], int size) {
for (int i = MAX_HEAP_SIZE / 2 - 1; i >= 0; i--)
siftDown(heap, i, size);
}
// 将元素下放至正确的位置,保证堆属性
void siftDown(Node heap[], int i, int size) {
int largest = i;
int left = LEFT_CHILD(i);
if (left < size && heap[left].data > heap[largest].data)
largest = left;
if (RIGHT_CHILD(i) < size && heap[RIGHT_CHILD(i)].data > heap[largest].data)
largest = RIGHT_CHILD(i);
if (largest != i) {
swap(&heap[i], &heap[largest]);
siftDown(heap, largest, size);
}
}
// 将新元素插入堆中
void insertNode(Node heap[], int value, int size) {
heap[size] = (Node){value, size};
siftUp(heap, size, size);
}
// 将堆顶元素与最后一个元素交换,然后缩小堆
void deleteTop(Node heap[], int size) {
if (size <= 1) return;
heap[0] = heap[size - 1]; // 将最后一个元素移到顶部
size--;
siftDown(heap, 0, size); // 下放堆顶元素到正确位置
}
// 查询堆顶元素
int getTopElement(Node heap[], int size) {
return heap[0].data;
}
// 检查是否已满
bool isFull(Node heap[], int size) {
return size == MAX_HEAP_SIZE;
}
// 简单的swap函数
void swap(Node *a, Node *b) {
int temp = a->index;
a->index = b->index;
b->index = temp;
}
int main() {
Node heap[MAX_HEAP_SIZE];
int size = 0;
// 插入元素示例
insertNode(heap, 50, size);
insertNode(heap, 30, size);
insertNode(heap, 70, size);
// 查询堆顶元素
printf("当前堆顶元素: %d\n", getTopElement(heap, size));
// 删除堆顶元素
deleteTop(heap, size);
printf("删除堆顶元素后堆顶元素: %d\n", getTopElement(heap, size));
return 0;
}
阅读全文