数据结构——堆

HZzzzzLu

发布于 2024-11-26 08:19:40

30000

代码可运行

文章被收录于专栏：codingcoding

运行总次数：0

代码可运行

堆的基本知识

堆（Heap）是一种特殊的树状数据结构。

主要特性

堆通常是一棵完全二叉树。
堆中的每一个节点必须满足特定顺序要求，以这个要求分出大根堆和小根堆。

大根堆：任何一个父节点的值都大于或等于它的子节点的值。

小根堆：任何一个父节点的值都小于或等于它的子节点的值。

基本操作

插入（Insertion）：在堆中添加新元素，同时保持堆的属性。
删除（Deletion）：通常指的是删除堆顶元素，然后重新调整堆以保持其属性。
查找堆顶元素（Find Top）：在最大堆中找到最大元素，在最小堆中找到最小元素。
堆调整（Heapify）：将堆的某一部分重新调整，以恢复堆属性。

应用场景

优先级队列
堆排序
内存管理

实现方式

一般用数组实现

父子节点之间的索引：

1.父节点：i

2.左节点：2 * i + 1

3.右节点 2 * i + 2

4通过子节点i 找父节点（i - 1）/ 2

堆的实现

堆的定义

typedef int HPDataType;

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

跟我们定义顺序表类似，一个动态申请的数组、有效数据个数、最大可容纳数据个数。

堆的初始化

将arr置空，将capacity和size置0。

//堆的初始化
void HPInit(HP* php)
{
	assert(php);

	php->arr = NULL;
	php->capacity = php->size = 0;
}

堆的销毁

将动态申请的数组free掉，把capacity和size置0。

// 堆的销毁
void HPDestroy(HP* php)
{
	assert(php);

	free(php->arr);
	php->capacity = php->size = 0;
}

堆的调整

调整算法用于堆的插入和删除后恢复堆的属性，但是用调整算法的前提是堆原本是有序的（大根堆或者小根堆）

向上调整

首先算出parent的索引，parent跟child比较，若child大于parent，则交换，然后更新parent、child，直到child小于等于0或者child小于parent了。


void AdjustUp(HPDataType* arr, int child)
{
	assert(arr);

	int parent = (child - 1) / 2;
	while(child > 0)// parent >= 0 是错的 parent = (0 - 1) / 2 == 0
	{
		if (arr[child] > arr[parent])
		{
			//交换
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;;
		}
	}
}

注意，循环条件不能用parent >= 0来判断，因为当child = 1，parent = 0时，child = parent后，child = 0，然后parent = (0 - 1) / 2 == 0,达不到理想终止的效果。（虽然最后循环也能停止，因为循环里arr[child] > arr[parent]不成立，break掉了，但是代码还是有问题的，要改正）

向下调整

向下调整与向上调整是类似的，但也有区别。

以大根堆为例，需要先找到左右孩子中较大的一个，再跟父亲比较。

//向下调整
void AdjustDown(HPDataType* arr, int size, int parent)
{
	assert(arr);

	
	int child = 2 * parent + 1;
	
	while (child < size)
	{
		//找两个孩子中较大的孩子 假设法 大的那个是左孩子
		if (child + 1 < size && 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 CheckCapacity(HP* php)
{
	assert(php);

	if (php->capacity == php->size)
	{
		int NewCapacity = (php->capacity == 0 ? 4 : 2 * php->capacity);
		HPDataType* tep = (HPDataType*)realloc(php->arr, NewCapacity * sizeof(HPDataType));
		if (tep == NULL)
		{
			perror("realloc fail!");
			return;
		}
		php->arr = tep;
		php->capacity = NewCapacity;
	}
}

// 堆的插入
void HPPush(HP* php, HPDataType x)
{
	assert(php);

	//插入之前检查空间是否足够
	CheckCapacity(php);

	php->arr[php->size++] = x;

	AdjustUp(php->arr, php->size-1);
}

堆的删除

堆的删除是删除堆顶的数据，首先将堆顶数据和最后一个数据交换，让size--，然后使用向下调整算法恢复堆的属性。

// 堆的删除 删除堆顶数据
//堆顶与尾交换 size-- 然后向下调整
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

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

取堆顶的数据

注意判断堆不为空就行了。

//取堆顶的数据
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->arr[0];
}

堆的判空

判断size == 0就行。

//堆的判空
bool HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

堆的应用

堆排序

堆排序主要利用堆的思想进行排序。

步骤：

1.建堆（升序建大堆；降序建小堆）

2.利用堆删除的思想来排序。（这也解释了为什么升序要建大堆，因为大堆确定了最大元素在堆顶）

向下调整建堆

从最后一个非叶子节点开始，向上遍历直到根节点，对每个节点进行调整，以确保其满足堆的性质。

步骤：

从最后一个非叶子节点开始，该节点的索引为 n/2 - 1，其中 n 是数组的长度。
对每个节点，检查其子节点，如果存在违反堆性质的情况（在最大堆中，子节点大于父节点；在最小堆中，子节点小于父节点），则交换父节点和较大的子节点。
继续这个过程，直到节点满足堆性质或到达根节点。

void AdjustDown(int* arr, int size, int parent)
{
	int child = 2 * parent + 1;

	while (child < size)
	{
		//假设法找出左右孩子中大的那个节点
		if (child + 1 < size && arr[child] < arr[child + 1])
		{
			child++;
		}

		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);

			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

时间复杂度O(n)

向上调整建堆

从第一个内部节点开始，向下遍历直到根节点，对每个节点进行调整。这种方法从底部开始，逐步向上调整节点。

步骤：

从第一个内部节点开始，该节点的索引为 n/2，其中 n 是数组的长度。
对每个节点，检查其父节点，如果当前节点违反了堆性质（在最大堆中，当前节点大于父节点；在最小堆中，当前节点小于父节点），则交换它们。
将交换后的节点视为新的当前节点，重复上述过程，直到当前节点满足堆性质或到达根节点。

void AdjustUp(HPDataType* arr, int child)
{
	assert(arr);

	int parent = (child - 1) / 2;
	while(child > 0)// parent >= 0 是错的 parent = (0 - 1) / 2 == 0
	{
		if (arr[child] > arr[parent])
		{
			//交换
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;;
		}
	}
}

时间复杂度O(nlogn)

对比两种建堆方式，我们应当使用向下调整建堆。

利用堆删除来排序

当数组建堆建好后，交换堆顶元素和最后一个元素，缩小堆的范围，向下重新调整堆，重复此过程，直到堆的大小为1，说明数组已经排序好了。

void Swap(int* p1, int* p2)
{
	int tep = *p1;
	*p1 = *p2;
	*p2 = tep;
}


void AdjustDown(int* arr, int size, int parent)
{
	int child = 2 * parent + 1;

	while (child < size)
	{
		//假设法找出左右孩子中大的那个节点
		if (child + 1 < size && 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 HeapSort(int* arr, int size)
{

	//向下建堆 
	//升序 建大堆
	//降序 建小堆
	for (int i = (size - 2) / 2; i >= 0; i--)
	{
		AdjustDown(arr, size, i);//大堆
	}

	int end = size - 1;
	while (end >= 0)
	{
		Swap(&arr[end], &arr[0]);
		AdjustDown(arr, end, 0);
		end--;
	}
}

堆排序的总时间复杂度是 O(n)（构建堆）+ O(nlogn)（堆排序过程），结果是 O(nlogn)。