当前位置:   article > 正文

【数据结构】【C语言】堆~动画超详细解读!

【数据结构】【C语言】堆~动画超详细解读!

1 什么是堆

  • 简单来说堆是二叉树的一种表示方式,它在逻辑上就是一颗完全二叉树,它在物理上却是一个数组,这么说可能有点抽象,我们原来学习的栈,队列,或者说顺序表,链表等等,他们的逻辑结构和物理结构是相同或者相似的,就会比较好理解一些,而在堆这里物理结构和逻辑结构截然不同,理解相对就会比较抽象一些,我们接着看

1.1 堆的逻辑结构和物理结构

  • 逻辑结构即我们想象的结构,就比方说我们早上在图书馆排队的时候,放个包在图书馆门口,人可能都不见了,这个时候我们逻辑上认为我们在排队,但物理上我们同学就可能在吃早饭上厕所啥的
  • 逻辑上我们想象这个数组是一个二叉树,并且像二叉树一样访问子节点或者父节点
  • 比方说我给出以下数组,它在逻辑上是这样表示的(当然哈,指针其实是不存在的,只是逻辑上我们看作其是父子关系):
    请添加图片描述

1.2 堆的访问

  • 既然堆是一颗货真价实的二叉树,可我们怎么像二叉树一样,通过父/子节点访问子/父节点呢?

在这里插入图片描述

  1. 通过父节点访问子节点:
    • 我们假设父节点的下标为3,我们想访问它的子节点,只需要把 父节点的下标 * 2 + 1父节点的下标 * 2 + 2 即可 即 7 或 8
  2. 通过子节点访问父节点
    • 我们假设子节点的下标为7,我们想访问它的父节点,只需要把 (子节点的下标 - 1) / 2 即可 即 3
    • 我们假设子节点的下表为8,我们想访问它的父节点,依旧只需要把 (子节点的下标 - 1) / 2 即可 依旧是 3

1.3 堆为什么物理结构上要用数组?

  • 事实上学习堆是为了学习堆排序打基础,在堆排序中,有时候需要频繁交换头尾节点,如果用数组,找节点就会方便很多,交换函数也很好写,效率会更高,用链表要不断去遍历,或者专门写个尾指针妥协,很没必要
  • 其次,如果我们用链式存储的话,访问子/父节点需要定义3个指针,需要多开辟很多空间
  • 堆一定是完全二叉树,用数组存放会很方便,其中不会有空节点,所有数据存储都是连续的

1.4 堆数据上的特点

  • 堆必须要始终满足满足:父节点值比子节点小或者父节点始终比子节点大
  • 我们称父节点值始终比子节点小的堆为小堆/小根堆
  • 我们称父节点值始终比子节点大的堆为大堆/大根堆

例如:
1.大堆:
在这里插入图片描述

2.小堆:
在这里插入图片描述

2 堆的实现

2.1 堆类型定义

//堆在物理上是一个数组,我们直接按数组的定义方式就行
//类型定义
typedef int HPDataType;

typedef struct Heap 
{
	HPDataType* data;
	int size;
	int capa;
}Heap;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

2.2 需要实现的接口

//交换函数
void Swap(HPDataType* x, HPDataType* y);

//向上调整(小堆)
void AdjustUp(HPDataType* data, int child);

//向下调整(小堆)
void AdjustDown(HPDataType* data, int size, int father);

//初始化堆
void HPInit(Heap* php);

//销毁堆
void HPDestroy(Heap* php);

//堆插入
void HPPush(Heap* php, HPDataType x);

//堆删除
void HPPop(Heap* php);

//堆顶
HPDataType HPTop(Heap* php);

//堆判空
bool HPEmpty(Heap* php);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

2.3 初始化堆

//像顺序表一样初始化就行
//初始化堆
void HPInit(HP* php)
{
	assert(php);
	php->a = (HPdatatype*)calloc(4, sizeof(HPdatatype));
	if (php->a == NULL)
	{
		perror("HPInit::calloc fail");
		exit(1);
	}
	php->capa = 4;
	php->size = 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

2.4 销毁堆

//同样,像顺序表一样销毁就行
//销毁堆
void HPdestory(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->capa = 0;
	php->size = 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

2.5 堆判空

//堆判空
bool HPEmpty(HP* php)
{
	assert(php);   //判空
	return php->size == 0;    //size是0就返回true
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

2.6 交换函数

//只是完成数据在空间上的交换
//交换函数
void Swap(HPdatatype* x, HPdatatype* y)
{
	HPdatatype tmp = *x;
	*x = *y;
	*y = tmp;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

2.7 向上调整(小堆)

  • 注意这里是重点
  • 向上调整会在很多地方用到,基本思想就是让本应该在上面的节点往上挪
//向上调整(小堆)
void AdjustUp(HPdatatype* a, int child)
{
	assert(a);//判空

	int father = (child - 1) / 2;//推算出父节点的位置
	while (father < child && a[father] > a[child])      //只要子节点比父节点还小,就让子节点和父节点交换
	{								               		//重复此步骤直到子节点大于父节点或者子节点和自己比较
		Swap(&a[child], &a[father]); 
		child = father;
		father = (child - 1) / 2;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

请添加图片描述

2.8 向下调整(小堆)

  • 注意这里是重点
  • 向下调整同样会在很多地方用到
//向下调整(小堆)
void AdjustDown(HPdatatype* a, int size, int father)
{
	assert(a);//判空

	int child = (father * 2) + 1;      //先假设比较小的是左子节点
	if (child + 1 < size && a[child] > a[child + 1])        //如果右子节点比左子节点大,注意要判断一下子节点是否会超范围
	{
		child++;        //把child改成右子节点
	}
	while (child < size && a[father] > a[child] )    //如果父节点一直比子节点大就不断交换下移
	{                                                //直到子节点超出size范围或者父节点比子节点小就停下
		Swap(&a[father], &a[child]);     //交换

		father = child;              //重新找到父节点(交换后的父节点应该是原来的子节点的位置)
		child = (father * 2) + 1;    //重新定位子节点
		if (child + 1 < size && a[child] > a[child + 1])    //如法炮制
		{
			child++;
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

请添加图片描述

2.9 堆插入

  • 堆插入一般插入到末尾,因为末尾很空,啥也没有,比较好插入,插在其他地方还得先挪动才可以插入
//堆插入
void HPPush(HP* php, HPdatatype x)
{
	assert(php);   //判空

	//堆扩容,这里像数组一样扩容就行
	if (php->capa == php->size)
	{
		HPdatatype* tmp = (HPdatatype*)realloc(php->a, 2 * php->size * sizeof(HPdatatype));
		if (tmp == NULL)
		{
			perror("HPPush::realloc fail");
			exit(1);
		}
		php->a = tmp;
		php->capa *= 2;
	}

	php->a[php->size] = x;    //将要插入的数据放到堆低
	
	AdjustUp(php->a, php->size);      //通过向上调整找到这个数据本应该在的位置

	php->size++;      //别忘了让size++
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

2.10 堆删除

  • 堆删除一般删除堆顶的数据,但不能简单地把堆顶置为空,而是要和末尾数据交换,再一点点下调
//堆删除
void HPPop(HP* php)
{
	assert(php);     //判空
	if (!HPEmpty(php))    //如果堆不是空堆
	{
		Swap(&php->a[0], &php->a[php->size - 1]);   //交换堆顶和末尾的数据

		AdjustDown(php->a, php->size - 1, 0);    //将堆顶的数据向下挪到合适的位置

		php->size--;   //别忘了size--
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

2.11 //堆顶

//取堆顶
HPdatatype HPTop(HP* php)
{
	assert(php);    //判空
	return HPEmpty(php) ? -1 : php->a[0];   //返回堆顶数据
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

  • 完整代码在最下面哦

佬!都看到这了,如果觉得有帮助的话一定要点赞啊佬 >v< !!!
放个卡密在这,感谢各位能看到这儿啦!
请添加图片描述


3 完整代码

3.1 heap.h

#pragma once

//头文件声明
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>

//类型定义
typedef int HPdatatype;

typedef struct Heap
{
	HPdatatype* a;
	int size;
	int capa;
}HP;

//函数申明

//交换函数
void Swap(HPDataType* x, HPDataType* y);

//向上调整(小堆)
void AdjustUp(HPDataType* data, int child);

//向下调整(小堆)
void AdjustDown(HPDataType* data, int size, int father);

//初始化堆
void HPInit(Heap* php);

//销毁堆
void HPDestroy(Heap* php);

//堆插入
void HPPush(Heap* php, HPDataType x);

//堆删除
void HPPop(Heap* php);

//堆顶
HPDataType HPTop(Heap* php);

//堆判空
bool HPEmpty(Heap* php);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

3.2 heap.c

#include "heap.h"

//初始化堆
void HPInit(HP* php)
{
	assert(php);
	php->a = (HPdatatype*)calloc(4, sizeof(HPdatatype));
	if (php->a == NULL)
	{
		perror("HPInit::calloc fail");
		exit(1);
	}
	php->capa = 4;
	php->size = 0;
}

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

	free(php->a);
	php->a = NULL;
	php->capa = 0;
	php->size = 0;
}

//堆判空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

//取堆顶
HPdatatype HPTop(HP* php)
{
	assert(php);
	return HPEmpty(php) ? -1 : php->a[0];
}

//交换
void Swap(HPdatatype* x, HPdatatype* y)
{
	HPdatatype tmp = *x;
	*x = *y;
	*y = tmp;
}

//向上调整(小堆)
void AdjustUp(HPdatatype* a, int child)
{
	assert(a);

	int father = (child - 1) / 2;
	while (father < child && a[father] > a[child])
	{
		Swap(&a[child], &a[father]);
		child = father;
		father = (child - 1) / 2;
	}
}

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

	//堆扩容
	if (php->capa == php->size)
	{
		HPdatatype* tmp = (HPdatatype*)realloc(php->a, 2 * php->size * sizeof(HPdatatype));
		if (tmp == NULL)
		{
			perror("HPPush::realloc fail");
			exit(1);
		}
		php->a = tmp;
		php->capa *= 2;
	}

	php->a[php->size] = x;
	
	AdjustUp(php->a, php->size);

	php->size++;
}

//向下调整(小堆)
void AdjustDown(HPdatatype* a, int size, int father)
{
	assert(a);

	int child = (father * 2) + 1;
	if (child + 1 < size && a[child] > a[child + 1])
	{
		child++;
	}
	while (child < size && a[father] > a[child] )
	{
		Swap(&a[father], &a[child]);

		father = child;
		child = (father * 2) + 1;
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++;
		}
	}
}

//堆删除
void HPPop(HP* php)
{
	assert(php);
	if (!HPEmpty(php))
	{
		Swap(&php->a[0], &php->a[php->size - 1]);

		AdjustDown(php->a, php->size - 1, 0);

		php->size--;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/661716
推荐阅读
相关标签
  

闽ICP备14008679号