开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【数据结构】堆的实现 -> 正文阅读

[数据结构与算法]【数据结构】堆的实现

堆的概念及结构

堆的逻辑结构与存储结构

堆的概念及结构

如果有一个关键码的集合K = { k0，k1 ，k2 ，…，k(n-1) }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： Ki <= K(2*i+1) 且 Ki <= K(2*i+2) (或Ki>=K(2*i+1) 且 Ki >= K(2*i+2)) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最小的堆叫做最小堆或小根堆，根节点最大的堆叫做最大堆或大根堆。

堆的性质：

? ? ? $\bullet$ ?堆中某个节点的值总是不大于或不小于其父节点的值；

? ? ? $\bullet$ ?堆总是一棵完全二叉树。

堆的逻辑结构与存储结构

由于我们是把一个集合中的元素按二叉树的顺序存储方式，存储在一个一维数组中，故堆的存储结构是一个一维数组，但我们是以二叉树的顺序存储方式方式进行存储，所以我们可以把这个一维数组想象成一颗二叉树，故堆的逻辑结构是一颗二叉树。

堆的实现

先创建堆的结构体：

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

再给定一个数组 arr，以建立小堆为例。

int a[] = { 27,15,19,18,28,34,65,49,25,37 };

注：这里创建堆的算法是将数组中的元素插入到堆中，然后再用向上调整算法来建堆，故先说明堆的插入。关于直接将数组改成堆，会在后面文章中给出。

堆的插入

先将元素插到堆的末尾，也就是在数组的后面插入元素，然后再用向上调整算法，将插入的元素调整至合适的位置，直到满足堆。

向上调整算法：

插入的元素不会影响从该元素到根上的其它元素，故只需要依次将插入的元素与其“父亲”相比即可。若小于则交换，然后向上迭代，否则该元素已经到达满足小堆的合适位置。

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

void AdjustUp(int* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])//若建大堆，这里 < 改成 > 
		{
			Swap(&a[child], &a[parent]);

			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;

	AdjustUp(hp->a, hp->size - 1);
}

堆的创建?

首先将堆初始化

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

此时堆为空，循环调用堆的插入算法即可

void HeapCreate(HP* hp, HPDataType* a, int n)
{
	assert(hp);
	assert(a);

	HeapInit(hp);
	for (int i = 0; i < n; i++)
	{
		HeapPush(hp, a[i]);
	}
}

堆的删除

堆的删除是删除堆顶的元素，首先将堆顶的元素与最后一个元素交换，然后删除最后一个元素，再使用向下调整算法，将交换上来的元素调整至合适的位置，直到满足堆。

向下调整算法：

由于是建小堆，将该元素与它最小的一个“孩子”相比，若”孩子“更小，则将其交换，然后向下迭代，否则该元素已经到达满足小堆的合适位置。

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
                                    //若建大堆这里的 < 改成 >
		if (child + 1 < n && a[child + 1] < a[child])
			child++;
		if (a[child] < a[parent])//若建大堆这里的 < 改成 >
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

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

	AdjustDown(hp->a, hp->size, 0);
}

获取堆顶的数据

直接返回数组的首元素。

HPDataType HeapTop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	return hp->a[0];
}

堆的数据个数

堆结构体中的 size 保存了现有元素个数，直接将其返回。

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

堆的判空

判断堆中的 size 是否为 0 即可。

bool HeapEmpty(HP* hp)
{
	return hp->size == 0;
}

堆的销毁

先将数组释放，再将堆的大小和容量置零。

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

实现堆的全部代码

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

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

void HeapCreate(HP* hp, HPDataType* a, int n);
void HeapDestroy(HP* hp);

void HeapPush(HP* hp, HPDataType x);
void AdjustUp(int* a, int child);
void HeapPop(HP* hp);
void AdjustDown(int* a, int n, int parent);

int HeapSize(HP* hp);
HPDataType HeapTop(HP* hp);
bool HeapEmpty(HP* hp);

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

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

void HeapCreate(HP* hp, HPDataType* a, int n)
{
	assert(hp);
	assert(a);
	HeapInit(hp);
	for (int i = 0; i < n; i++)
	{
		HeapPush(hp, a[i]);
	}
}

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

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

			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;

	AdjustUp(hp->a, hp->size - 1);
}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
			child++;
		if (a[child] < a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

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

	AdjustDown(hp->a, hp->size, 0);
}

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

HPDataType HeapTop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	return hp->a[0];
}

bool HeapEmpty(HP* hp)
{
	return hp->size == 0;
}

测试用例

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

void TestHeap()
{
    int a[] = { 27,15,19,18,28,34,65,49,25,37 };
	HP hp;
	HeapCreate(&hp, a, sizeof(a)/sizeof(a[0]));
    HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapDestroy(&hp);
}

int main()
{
	TestHeap();
	return 0;
}