虫子 堆 基本算法

举报
虫子VV 发表于 2022/06/22 23:45:54 2022/06/22
【摘要】 堆 堆的概念及结构 堆的性质 堆的结构（这里实现大堆） 堆的结构体 堆初始化函数HeapInit 堆销毁函数HeapDestroy 堆打印函数HeapPrint 向上调整函数AdjustUp 堆插入函数HeapPush 判断堆是否为空函数HeapErmpy 返回堆大小函数HeapSize 交换函数Swap 向下调整函数AdjustDown 堆删除函数HeapPop 代码 Heap.h He...

堆

数据结构中的堆不同于操作系统中的堆（操作系统中的堆是用来存储动态内存的），数据结构中的堆是数据的存储方式。数据结构中的堆是==完全二叉树==

既然堆是完全二叉树的形式存储的那么就非常适合用数组的方式来表示

堆的概念及结构

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

大堆：树中一个树及子树中，任何一个父亲都大于等于孩子

小堆：树中一个树及子树中，任何一个父亲都小于等于孩子

堆的性质

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

堆的结构（这里实现大堆）

image-20211108081113661

==既然还是数组的结构的话就还是顺序表的处理方式，数组指针，size，capacity。虽然物理上我们是用顺序表的方式来表示，但是他实际上表示的数据是完全二叉树。==

堆的结构体

typedef int HPDataType;

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

堆初始化函数HeapInit

就是一个指向NULL的数组，size 和 capacity都为零

//堆初始化函数
void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

堆销毁函数HeapDestroy

由于数组是动态开辟的，所以用完后需要销毁的，不然会内存泄漏

//堆销毁函数
void HeapDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->size = hp->capacity = 0;
}

堆打印函数HeapPrint

可以想象成一种快速调试，类似于单片机中的串口打印看数据收发情况

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

向上调整函数AdjustUp

为了不影响数据的存储形式（大堆还得是大堆），插入数据就不能破坏大堆的形式，我们需要把堆插入函数中的数据调整给剥离出来

==我们可以看到插入的这个数据对其他的节点并没有什么影响，有影响的只是这个节点到根这条路径上的节点，如何解决对这条路径的影响呢，我们可以形象的看到仅仅是在这条路径上进行向上调整==

通过parent = （child-1）/2 找到父亲节点，与之进行比较，然后父亲小就交换位置（大堆），然后交换后就在找上面的父亲节点，直到找到父亲大于孩子，就不交换了

image-20211108115306980

//向上调整函数
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[parent] < a[child])//父亲小于孩子就交换（大堆）
		{
			a[parent] = a[parent] ^ a[child];
			a[child] = a[parent] ^ a[child];
			a[parent] = a[parent] ^ a[child];
			//交换好后重新称呼一下孩子与父亲
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}

	}
}

堆插入函数HeapPush

image-20211108163302928

//堆插入函数（要保持原来形式，大堆还是大堆，小堆就还是小堆）
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)
		{
			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);//child下标
}

判断堆是否为空函数HeapErmpy

//判断堆是否为空函数
bool HeapErmpy(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}

返回堆大小函数HeapSize

//返回堆大小函数
int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

==下面还会用到交换函数，上面也有那么我们不妨把他剥离出来封装一下，就不需要重复写了==

交换函数Swap

//交换函数
void Swap(HPDataType* px, HPDataType* py)
{
	*px = *px ^ *py;
	*py = *px ^ *py;
	*px = *px ^ *py;
}

向下调整函数AdjustDown

image-20211108223143528

//向下调整函数
void AdjustDown(HPDataType* a, int size, int parent)
{
	assert(a);
	//创建一个孩子变量，有两个孩子就在这个上加1就行
	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;
		}
	}
}

堆删除函数HeapPop

我们可以认为假想根和堆的最后一个元素交换后，把最后一个删除，然后再对堆进行操作，你会发现，我们没有破坏原来的整体结构

image-20211108223334078

//堆删除函数（删除的是堆顶数据也就是取最值）
//还有不可能一直删的所以我们需要一个判空函数
void HeapPop(HP* hp)
{
	assert(hp);
	assert(!HeapErmpy(hp));
	//根和堆最后一个元素交换
	Swap(&hp->a[0],&hp->a[hp->size-1]);
	//把最后一个删除，就是我们想要删除的元素
	hp->size--;
	//向下调整
	AdjustDown(hp->a,hp->size,0);
}

代码

Heap.h

#pragma once

#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;

//堆初始化函数
extern void HeapInit(HP* hp);
//堆销毁函数
extern void HeapDestroy(HP* hp);
//向上调整函数
extern void AdjustUp(HPDataType* a,int child);
//堆插入函数
extern void HeapPush(HP* hp,HPDataType x);
//堆打印函数
extern void HeapPrint(HP* hp);
//向下调整函数
extern void AdjustDown(HPDataType* a, int size, int parent);
//堆删除函数
extern void HeapPop(HP* hp);
//判断堆是否为空函数
extern bool HeapErmpy(HP* hp);
//交换函数
extern void Swap(HPDataType* px, HPDataType* py);
//返回堆大小函数
extern int HeapSize(HP* hp);

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Heap.h"

//堆初始化函数
void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}
//堆销毁函数
void HeapDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->size = hp->capacity = 0;
}

//向上调整函数
void AdjustUp(HPDataType* a, int size, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[parent] < a[child])//父亲小于孩子就交换（大堆）
		{
			Swap(&a[parent], &a[child]);
			//交换好后重新称呼一下孩子与父亲
			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)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		//增容成功
		hp->a = tmp;
		hp->capacity = newcapacity;		
	}
	//放数据
	hp->a[hp->size] = x;
	hp->size++;
	//实现大堆
	//这个部分的向上调整其他地方也用的到就把他剥离出来
	//向上调整一下堆的数据形式，使他还是大堆的形式
	AdjustUp(hp->a, hp->size, hp->size - 1);
}
//堆打印函数
void HeapPrint(HP* hp)
{
	assert(hp);
	int i = 0;
	for (i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}
//判断堆是否为空函数
bool HeapErmpy(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}
//返回堆大小函数
int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}
//交换函数
void Swap(HPDataType* px, HPDataType* py)
{
	*px = *px ^ *py;
	*py = *px ^ *py;
	*px = *px ^ *py;
}
//向下调整函数
void AdjustDown(HPDataType* a, int size, int parent)
{
	assert(a);
	//创建一个孩子变量，有两个孩子就在这个上加1就行
	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 HeapPop(HP* hp)
{
	assert(hp);
	assert(!HeapErmpy(hp));
	//根和堆最后一个元素交换
	Swap(&hp->a[0],&hp->a[hp->size-1]);
	//把最后一个删除，就是我们想要删除的元素
	hp->size--;
	//向下调整
	AdjustDown(hp->a,hp->size,0);
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Heap.h"

void test()
{
	int a[] = { 70,56,30,25,15,75 };
	HP hp;
	HeapInit(&hp);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(&hp, a[i]);
	}
	HeapPrint(&hp);
	HeapPop(&hp);
	HeapPrint(&hp);
	HeapDestroy(&hp);
}


int main()
{
	test();
	return 0;
}
【版权声明】本文为华为云社区用户原创内容，未经允许不得转载，如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入