数据结构——堆

前言

在计算机科学中，数据结构（data structure）是一种数据组织、管理和存储的格式。它是相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术相关。 数据结构研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系。它包含三个方面的内容：即数据的逻辑结构、数据的存储结构和数据的操作，只有这三个方面的内容完全相同，才能成为完全相同的数据结构。

数据结构是计算机四大件之一，是与计算机组成原理、操作系统、计算机网络齐名的存在，因此数据结构的重要性不言而喻。

本章将带领大家去了解堆这一重要的数据结构。

概念

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。现实中我们通常把堆（一种二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆总是满足下列性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值；
• 堆总是一棵完全二叉树。

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。这里我们讨论的是二叉堆。堆的实质是把一个数组中的元素按照特定的方式，也就是完全二叉树的方式进行排列。

结构

堆的底层逻辑为数组，因此定义堆的结构为：

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

堆的结构清晰明了，最为重要的是排列方式：每一个父节点都大于（小于）其子节点。

实现

小根堆和大根堆的实现基本相同，今天我们实现小根堆。具体的函数接口如下：

//默认初始化堆
void HPInit(HP* php);
//堆的插⼊
void HPPush(HP* php, int x);
//堆的删除
int HPPop(HP* php);
//判空
bool HPEmpty(HP* php);
//求size
int HPSize(HP* php);
//堆的销毁
void HPDestroy(HP* php);

//向上调整算法
void AdjustUp(int* arr, int child);
//向下调整算法
void AdjustDown(int* arr, int n, int parent);
//利⽤给定数组初始化堆
void HPInitArray(HP* php, int* arr, int n);

在堆的实现中，最为重要的是就是向上调整算法和向下调整算法。

1.向上调整算法

向上调整算法 • 先将元素插入到堆的末尾,即最后一个孩子之后 • 插入之后如果堆的性质遭到破坏，将新插入结点顺着其双双亲往上调整到合适位置即可

void AdjustUp(int* 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;
		}
	}
}

向上调整算法指的是通过给定的子节点向上找出父节点，判断子节点与父节点的大小是否满足我们所建的堆，如果不满足则交换大小，并使此时的父节点成为子节点，继续向上判断，直到满足堆的结构或者达到子节点达到根节点的位置。

2.向下调整算法

向下调整算法 • 将堆顶元素与堆中最后一个元素进⾏交换 • 删除堆中最后一个元素 • 将堆顶元素向下调整到满足堆特性为止

void AdjustDown(int* arr, int n, int parent)
{
	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;
		}
	}
}

向下调整算法是通过给出一个父节点，与它的两个子节点中较小的那一个进行比较，若是比较小的子节点大，则交换两者的位置，并使该子节点成为新的父节点，直到父节点比两个子节点都小或是子节点的大小超过了数组的大小。

3.堆的初始化

介绍完堆的两个最重要的算法之后我们来开始实现一个堆。

void HPInit(HP* php)
{
	php->arr = (int*)malloc(sizeof(int) * 4);
	if (php->arr == NULL)
	{
		printf("malloc fail!\n");
		exit(-1);
	}
	php->size = 0;
	php->capacity = 4;
}

堆的初始化与顺序表一样，malloc动态开辟一块空间，并把空间的大小赋给capacity，size是堆中元素的数量。

4.堆的插入

void HPPush(HP* php, int x)
{
	if (php->capacity == php->size)
	{
		Dilatation(php);
	}

	php->arr[php->size] = x;
	AdjustUp(php->arr, php->size);
	php->size++;
}

堆的插入与正常的顺序表尾插一样，先判断数组是否满了，若满了则进行扩容操作。与顺序表不同的是堆的插入数据后要进行向上调整，使堆中的元素符合规则。

5.堆的删除

int HPPop(HP* php)
{
	if (php->size == 0)
	{
		printf("empty heap!\n");
		return;
	}

	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	AdjustDown(php->arr, php->size - 1, 0);
}

堆的删除是把堆的第一个元素与最后一个元素交换，并使size--，在对第一个元素进行向下调整，使堆中的元素都符合堆的规则。要注意的是需要先判断堆中的元素个数是否为0；

6.堆的销毁

void HPDestroy(HP* php)
{
	free(php->arr);
	php->capacity = 0;
	php->size = 0;
}

与顺序表的销毁相同，只需要free掉动态开辟的空间并把capacity和size置0即可。

对于判空以及获得堆中元素个数等函数接口都只需要调出size即可，不再单独展示代码。

7.利用给定的数组初始化堆

给定一个数组，我们该如何使其成为一个堆呢？思路很简单，对数组中的每一个元素都调用一次向上调整算法即可，但是我们知道，向上调整的时间复杂度很高，那有没有其他的方法呢?答案是有的，那就是用向下调整算法，向下调整算法的时间复杂度是低于向上调整算法的。那么我们该如何利用向下调整算法来使一个数组变成堆的结构，先看下面代码：

void HPInitArray(HP* php, int* arr, int n)
{
	for (int i = (n - 1 - 1) / 2; i--; i >= 0)
	{
		AdjustDown(arr, n, i);
	}

	php->arr = arr;
	php->capacity = n;
	php->size = n;
}

我们通过最后一个元素找到它的父节点，对其进行向下调整，再依次对其前面的每一个元素都进行向下调整，这样即可完成我们的“建堆”。

用途

通过对堆的学习和了解，我们可以通过堆来对数组进行排序，也就是我们八大排序算法中的堆排序。此外还可以用来解决TOP-K问题，也就是在非常多的数据找找到最大或最小的若干个数据。堆是一个非常重要的数据结构，它是一种完全二叉树，对我们将来学习二叉树也有很深的影响。更多关于堆的奥妙还需要大家进行更深入的学习。

尾声

关于堆这一数据结构，我们已经了解完了。但是想要用好堆，用对堆还是一件难事，需要我们通过大量的练习去更加深刻的了解它。

若有纰漏或不足之处欢迎大家在评论区留言或者私信，同时也欢迎各位一起探讨学习。感谢您的观看！