[数据结构]堆

堆，本质是一颗完全二叉树。属于非线性结构。

代码实现可参考树的代码。

函数介绍:

//此堆是小堆,大堆操作部分与小堆相反
void InitHeap(Heap* cat)
{
	assert(cat);
	cat->arr = NULL;
	cat->capacity = cat->size = 0;
}
void DestroyHeap(Heap* cat)
{
	assert(cat);
	if (cat->arr)
		free(cat->arr);
	cat->arr = NULL;
}
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void AdjustUp(Type* arr, int child)//小堆
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* cat, Type x)
{
	assert(cat);
	if (cat->capacity == cat->size)
	{
		int newcapacity = cat->capacity == 0 ? 4 : 2 * cat->capacity;
		Type* tmp = (Type*)realloc(cat->arr, newcapacity * sizeof(Type));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		cat->capacity = newcapacity;
		cat->arr = tmp;
	}
	cat->arr[cat->size++] = x;
	AdjutUp(cat->arr, cat->size);
}
void AdjustDown(Type* arr, int parent, int n)//小堆
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] > arr[child + 1])//找
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPop(Heap* cat)
{
	assert(cat);
	Swap(&cat->arr[0], &cat->arr[cat->size - 1]);
	--cat->size;
	AdjustDown(cat->arr, 0, cat->size - 1);
}
//判空
bool HeapEmpty(Heap* cat)
{
	assert(cat);
	return cat->size == 0;
}
//输出堆顶数据
Type HeapTop(Heap* cat)
{
	assert(cat);
	return cat->arr[0];
}
//打印堆可用三种遍历方式打印或者树的层序遍历，此处省略

头文件介绍：

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int Type;
typedef struct Heap {
	Type* arr;
	int capacity;
	int size;
}Heap;
void InitHeap(Heap* cat);
void DestroyHeap(Heap* cat);
void Swap(int* x, int* y);
void AdjustUp(Type* arr, int child);
void HeapPush(Heap* cat, Type x);
void AdjustDown(Type* arr, int parent, int n);
void HeapPop(Heap* cat);
bool HeapEmpty(Heap* cat);
Type HeapTop(Heap* cat);

谢谢观看!