实现一个基于数组的大根堆
最大堆是一种常见的数据结构，用于维护一组数据中的最大值。在这篇文章中，我们将实现一个基于数组的最大堆，并提供添加元素和删除堆顶元素的操作。
结构定义
首先，我们定义了一个 Heap 结构体，用于表示最大堆，其中包含一个数组用于存储堆中的元素，以及堆的容量和当前元素个数。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool>#define TYPE int
#define swap(a,b) {typeof(a) t=(a);(a)=(b);(b)=t;}typedef struct Heap
{TYPE *arr;int cap;int cnt;
} Heap;
创建堆
我们实现了一个 creat_heap 函数，用于创建一个指定容量的最大堆，并初始化堆的相关字段。
Heap *creat_heap(int cap)
{Heap *heap = malloc(sizeof(Heap));heap->arr = malloc(sizeof(TYPE) * (cap + 1));heap->cnt = 0;heap->cap = cap;return heap;
}
添加元素
我们实现了一个 add_heap 函数，用于向堆中添加元素，并在添加后继续调整堆以保持最大堆的性质。
bool add_heap(Heap *heap,TYPE data)
{if(full_heap(heap))return false;heap->arr[++heap->cnt]=data;//添加后继续调整堆int i=heap->cnt;while(i>1){if(heap->arr[i/2] < heap->arr[i])swap(heap->arr[i/2],heap->arr[i]);i=i/2;}return true;
}
删除堆顶元素
我们实现了一个 del_heap 函数，用于删除堆顶元素，并在删除后调整堆以保持最大堆的性质。
bool del_heap(Heap *heap)
{if(empty_heap(heap))return false;swap(heap->arr[1],heap->arr[heap->cnt]);//交换堆顶元素和堆最后一个元素heap->cnt--;
//删除最后一个元素后调整堆
//从上往下调整int i=1;while(i<heap->cnt){if(i*2+1<heap->cnt)//判断是否存在右孩子节点{if(heap->arr[i*2+1]>heap->arr[i*2]&&heap->arr[i*2+1]>heap->arr[i]){swap(heap->arr[i],heap->arr[i*2+1]);i=i*2+1;}else if(heap->arr[i*2]>heap->arr[i*2+1] && heap->arr[i*2]>heap->arr[i]){swap(heap->arr[i],heap->arr[i*2]);i=i*2;}elsebreak;}else if(i*2<heap->cnt)//判断是否存在左孩子结点{if(heap->arr[i*2]>heap->arr[i]){swap(heap->arr[i],heap->arr[i*2]) i=i*2;}elsebreak;}elsebreak;}return true;
}
示例用法
我们在 main 函数中演示了如何使用上述堆操作函数，创建一个容量为 10 的最大堆，并添加随机元素，然后删除堆顶元素。
int main(int argc, const char* argv[])
{Heap *heap = creat_heap(10);for (int i = 0; i < 10; i++){TYPE data = 0;data = rand() % 100;add_heap(heap, data);}show_heap(heap);del_heap(heap);show_heap(heap);}
这篇博客文章展示了如何实现一个基于数组的最大堆，并提供了添加元素和删除堆顶元素的操作。希望这个示例对您有所帮助。如果您有任何问题或需要进一步帮助，请随时告诉我。