数据结构:堆的三部曲 (一)堆的实现

发布时间:2024年01月01日

1.堆的结构

1.1堆的定义理解

堆的逻辑结构为一颗完全二叉树,堆对于数据存储有一定的要求:这这棵树的任意一颗子树的根节点的值小于等于(或大于等于)其孩子节点的值。我们将根节点最大的堆叫做小堆,把根节点最大的堆叫做大堆。
堆的存储结构结构为数组,我们将堆的元素存储在一个数组之中。由于堆是完全二叉树,所以其节点下标之间满足以下关系:
parent = (child-1) / 2
leftChild = parent2 + 1
rightChild = parent
2 + 2 = leftChild + 1

堆的结构如图:
在这里插入图片描述

注意:堆规定的是父亲和孩子之间值的关系,并没有规定左右孩子值之间的关系。比如下图,我们对于15这个父节点的左右孩子大小没有要求,两种情况都可以,因此我们只需要维护父亲和孩子的关系即可。
在这里插入图片描述

2.堆的实现(以小根堆为例)

2.1 堆结构体的定义

由于堆是使用数组来存储的,因此堆的结构定义和顺序表相同,首先需要定义一个数据类型的指针,然后还需要定义int类型的size和capacity,用来记录当前有多少个节点以及当前最多能存储多少节点,当空间不足时我们就可以扩容操作。

typedef int HpDataType;
typedef struct Heap
{
	HpDataType* a;
	int size;
	int capacity;
}HP;

2.2 堆的插入

堆的插入的前提是插入前的二叉树是堆,因此插入数据后只需要保持其父亲节点和孩子节点的关系。由于使用数组存储,因此在size位置插入后,就需要开始调整使插入后仍为堆。

交换函数

void Swap(HpDataType* x, HpDataType* y)
{
	HpDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

向上调整算法

由于是从插入的那个孩子处开始调整,所以需要传入当时的下标。
child即为最后一个节点的下标。由于需要维护每一个父亲和孩子的关系,因此需要用到循环。如果新插入的节点的值比父节点的值小,那么交换它们的值,如果比其的父节点的值大,那么插入节点后的堆仍为小堆,不需要调整,退出循环。考虑最坏情况,如果插入的节点比第一个节点的值都小,那么就需要一直交换,当最后一个节点也调整后,不满足条件从而退出循环,那么这个最坏的结果结束后的child即为最终的循环结束条件,此时child为0,因此循环进行条件为child>0,结束条件为child<=0。

void AdjustUp(HpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

插入函数的代码

void HPPush(HP* hp, HpDataType x)
{
	assert(hp);
	int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
	//空间如果不足则扩容
	if (hp->capacity == hp->size)
	{
		HpDataType* tmp = (HpDataType*)realloc(hp->a, newcapacity*sizeof(HpDataType));
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size - 1);
}

2.3 堆的删除

堆的删除为删除堆顶元素。
如果我们直接使用数据移动覆盖的删除方法,那么基本所有的父子关系将会被打乱,这样堆就会被完全破坏,而顺序表删除最后一个元素很容易,因此我们可以将第一个节点和最后一个节点交换,再删除最后一个节点,这样不仅更加简便,而且根节点的左右子树仍为堆,我们只需要将根节点向下调整即可调整为堆。

向下调整算法:

那么如何实现向下调整算法呢?
我们需要让每一颗子树的根节点都为该树的最小值,由于堆没有规定左右孩子之间的关系,因此如果需要向下调整交换时,需要判断该节点的左右孩子的最小值。如果不需要交换,即该节点比孩子节点小,那么就证明此时为堆,结束循环。考虑最坏情况,直到交换到叶子节点才能结束,那么如何判断叶子节点呢?叶子节点是没有孩子的节点,也就是其孩子的下标超出了size的大小,因此通过child和size的大小可以判断是否为叶子节点。

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

	while (child < size)
	{
		//假设左孩子小,如果假设错误则交换
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

删除函数的代码:

void HPPop(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);

	Swap(&hp->a[0], hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);
}

2.4其他操作

2.4.1取堆顶元素

int HPTop(HP* hp)
{
	assert(hp);

	return hp->a[0];
}

2.4.2堆的节点个数

int HPSize(HP* hp)
{
	assert(hp);

	return hp->size;
}

2.4.3堆是否为空判断

bool IsEmpty(HP* hp)
{
	assert(hp);

	return hp->size == 0;
}

3.测试以及完整源代码实现

3.1测试代码

int main()
{
	int a[] = { 3,5,2,7,9,4,1 };
	HP hp;
	HPinit(&hp);
	//建堆
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}
	//打印堆
	for (int i = 0; i < hp.size; i++)
	{
		printf("%d ", hp.a[i]);
	}
	printf("\n");
	//类似堆排序
	while (!IsEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}
	printf("\n");
	//类似top  k
	//int k = 3;
	//while (k--)
	//{
	//	printf("%d ", HPTop(&hp));
	//	HPPop(&hp);
	//}

	HPDestroy(&hp);
	return 0;
}

运行结果如下:
在这里插入图片描述

3.2完整代码实现

heap.c

#pragma once

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

typedef int HpDataType;
typedef struct Heap
{
	HpDataType* a;
	int size;
	int capacity;
}HP;

void HPinit(HP* hp);
void HPDestroy(HP* hp);
void HPPush(HP* hp, HpDataType x);
void HPPop(HP* hp);
int HPTop(HP* hp);
bool IsEmpty(HP* hp);
int HPSize(HP* hp);

heap.c

//小堆的实现
void HPinit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

void HPDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

void Swap(HpDataType* x, HpDataType* y)
{
	HpDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

void AdjustUp(HpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HPPush(HP* hp, HpDataType x)
{
	assert(hp);
	if (hp->capacity == hp->size)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HpDataType* tmp = (HpDataType*)realloc(hp->a, newcapacity * sizeof(HpDataType));
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size - 1);
}

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

	while (child < size)
	{
		//假设左孩子小,如果假设错误则交换
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HPPop(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);

	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);
}

int HPTop(HP* hp)
{
	assert(hp);

	return hp->a[0];
}

bool IsEmpty(HP* hp)
{
	assert(hp);

	return hp->size == 0;
}

int HPSize(HP* hp)
{
	assert(hp);

	return hp->size;
}

main.c

#include "heap.h"

int main()
{
	int a[] = { 3,5,2,7,9,4,1 };
	HP hp;
	HPinit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}
	printf("建堆如下:");
	for (int i = 0; i < hp.size; i++)
	{
		printf("%d ", hp.a[i]);
	}
	printf("\n");
	printf("依次取堆顶元素:");
	while (!IsEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}
	printf("\n");
	//int k = 3;
	//while (k--)
	//{
	//	printf("%d ", HPTop(&hp));
	//	HPPop(&hp);
	//}
	HPDestroy(&hp);
	return 0;
}

以上就是本次说有内容,谢谢观看。

文章来源:https://blog.csdn.net/2303_79175956/article/details/135317921
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。