数据结构——堆

定义：堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。 故通常我们用完全二叉树来维护一个一维数组。

分类 : 按照堆的特点可以把堆分为大根堆和小根堆
大根堆：每个结点的值都大于或等于其左右孩子结点的值
小根堆：每个结点的值都小于或等于其左右孩子结点的值

二叉树的性质：

对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：                                                                                                          1. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点                           2. 若 2i+1 < n, 则左孩子编号：2*i + 1.                                                                                               3. 若 2i+2 < n, 则右孩子编号：2*i + 2。

堆的关键操作：（以小根堆为例）

1.下沉操作down
对于一个节点，我们判断其节点值与左右节点的值相比较，如果当前节点的值不满足都小于或等于其左右孩子结点的值， 那么我们将节点与左右节点中较小的那个进行交换操作，由于进行了交换，故当前这棵子树中满足了小顶堆的特点，但由于交换了位置，故需要判断被交换位置后的子树位置此时的节点与其新左右孩子的节点值是否满足小顶堆。

2.上浮操作up
对于一个节点我们与其父节点进行比较，如果当前的父节点比其节点值大，则不满足小顶堆的条件，故此时这两个节点需要进行交互，交换完毕后的成为新的父节点，此时由于位置变动，其需要继续与原本父节点的父节点进行比较，直到都满足堆条件为止。

堆的实现：

头文件 heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
}Heap;

//初始化
void HeapInit(Heap* hp);

//销毁
void HeapDestroy(Heap* hp);

//插入
void HeapPush(Heap* hp, HPDataType x);

//打印
void HeapPrint(Heap* hp);

//删除堆顶
void HeapPop(Heap* hp);

//取堆顶元素
int HeapTop(Heap* hp);

//数据个数
int HeapSize(Heap* hp);

//堆的判空
bool HeapEmpty(Heap* hp);

void Swap(HPDataType* x, HPDataType* y);
void Up(HPDataType* arr, int child);
void Down(HPDataType* arr, int parent, int n);

源文件 heap.c 

#include"heap.h"

//初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->arr = NULL;
	hp->size = hp->capacity = 0;
}

//销毁
void HeapDestroy(Heap* hp)
{
	assert(hp);
	if (hp->arr)
		free(hp->arr);
	hp->arr = NULL;
	hp->size = hp->capacity = 0;
}

//打印
void HeapPrint(Heap* hp)
{
	assert(hp);
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->arr[i]);
	}
	printf("\n");
}

//交换两数
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

//向上调整
void Up(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child)
	{
		//大根堆: >   ,  小根堆：<
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)//空间不足
	{
		int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
		HPDataType* tmp = (HPDataType*)realloc(hp->arr, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		hp->arr = tmp;
		hp->capacity = newcapacity;//扩容成功
	}
	hp->arr[hp->size] = x;
	Up(hp->arr, hp->size);
	hp->size++;
}

//数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

//堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

//向下调整
void Down(HPDataType* arr, int parent, int n)
{
	int child = 2 * parent + 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 = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

//删除堆顶
void HeapPop(Heap* hp)
{
	assert(!HeapEmpty(hp));
	Swap(&hp->arr[0], &hp->arr[hp->size - 1]);
	hp->size--;
	Down(hp->arr, 0, hp->size);
}

//取堆顶元素
int HeapTop(Heap* hp)
{
	assert(!HeapEmpty(hp));
	return hp->arr[0];
}