实现一个基于数组的大根堆

实现一个基于数组的大根堆

最大堆是一种常见的数据结构，用于维护一组数据中的最大值。在这篇文章中，我们将实现一个基于数组的最大堆，并提供添加元素和删除堆顶元素的操作。

结构定义

首先，我们定义了一个 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;
			}
			else
				break;
		}
		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;
			}
			else
				break;
		}
		else
			break;
	}
	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);

}

这篇博客文章展示了如何实现一个基于数组的最大堆，并提供了添加元素和删除堆顶元素的操作。希望这个示例对您有所帮助。如果您有任何问题或需要进一步帮助，请随时告诉我。