二叉树 – 堆 | 数据结构中的小技巧大作用

在这里插入图片描述

?? 江池俊：
个人主页

??个人专栏：
?数据结构冒险记
?C语言进阶之路

?? 有航道的人，再渺小也不会迷途。

在这里插入图片描述

文章目录

- 一、堆的概念及介绍
- 二、结构图示
- 三、堆的代码实现（图解）
- - 3.1 创建堆结构体即接口
  - 3.2 堆的初始化 && 交换两个数（用于parent 和 child 的交换）
  - 3.3 堆的向上调整
  - 3.4 堆向下调整算法（以小堆为例）
  - 3.5 堆的创建
  - - 【向上调整建堆时间复杂度】
    - 【向下调整建堆时间复杂度】
  - 3.6 堆的插入
  - 3.7 堆的删除
  - 3.8 取堆顶的数据
  - 3.9 求堆的数据个数
  - 3.10 堆的判空
- 四、源代码
- - 4.1 Heap.h文件
  - 4.2 Heap.c文件
  - 4.3 Test.c文件

一、堆的概念及介绍

堆(Heap)是计算机科学中一类特殊的数据结构的统称。
堆通常是一个可以被看做一棵完全二叉树的数组。

需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆满足下列性质：

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

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
在这里插入图片描述

二、结构图示

二叉堆是一颗完全二叉树，且堆中某个节点的值总是不大于其父节点的值，该完全二叉树的深度为 k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边。

其中堆的根节点最大称为最大堆，如下图所示：
在这里插入图片描述
我们可以使用数组存储二叉堆，右边的标号是数组的索引。

在这里插入图片描述

假设当前元素的索引位置为 i，可以得到规律：

parent(i) = i/2（取整）
left child(i) = 2*i+1
right child(i) = 2*i +2

三、堆的代码实现（图解）

3.1 创建堆结构体即接口

typedef int HPDataType; //数据元素类型
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap; //堆的结构

//堆的初始化 (可要可不要)
void HeapInit(Heap* hp);
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

3.2 堆的初始化 && 交换两个数（用于parent 和 child 的交换）

// 堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);

	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}
//交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

3.3 堆的向上调整

注意：此算法的前提是 在进行向上调整前此树已经是堆。
向上调整操作用于在插入新元素时保持堆的性质。

算法思想如下：

首先，计算给定节点的父节点索引。如果当前节点是根节点（即索引为0），则没有父节点，不需要进行向上调整。

然后，进入一个循环，条件是当前节点的索引大于0。这是因为根节点已经是堆中的最大值（对于大顶堆）或最小值（对于小顶堆），无需再向上调整。

在循环中，比较当前节点和其父节点的值。如果当前节点的值小于其父节点的值（对于大顶堆）或大于其父节点的值（对于小顶堆），则需要进行向上调整。

交换当前节点和其父节点的值，将父节点移动到正确的位置。然后更新当前节点的索引为父节点的索引，并重新计算父节点的索引。

如果当前节点的值大于或等于其父节点的值（对于大顶堆）或小于或等于其父节点的值（对于小顶堆），则说明已经到达了正确的位置，可以跳出循环。

通过以上步骤，可以实现向上调整操作，确保堆的性质得到维护。

//向上调整 --- 插入时使用，保证堆的结构
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while(parent >= 0)
	while (child > 0)
	{
		if (a[child] < a[parent]) //< 改成 > 就是大堆的向上调整
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

时间复杂度分析：
最坏的情况下是从第一个非叶子节点一路比较到根节点，比较的次数为完全二叉树的高度-1，即时间复杂度为 O(log₂N)

3.4 堆向下调整算法（以小堆为例）

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。
向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

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

在这里插入图片描述

算法思想如下：

假设当前节点的左孩子为最小值节点。

判断当前节点是否有右孩子，如果有且右孩子的值小于左孩子的值，则将右孩子的下标赋值给child。

如果当前节点的值大于child节点的值，说明需要向下调整，交换当前节点和child节点的值。

更新parent为child，继续向下调整。

如果当前节点的值小于等于child节点的值，说明已经找到合适的位置，跳出循环。

通过以上步骤，可以实现向下调整操作，确保堆的性质得到维护。

//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{
	//假设左孩子小
	int child = parent * 2 + 1;
	while (child < size)
	{
		//如果右孩子更小，则将child的下标置为右孩子的下标
		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;
		}
	}
}

时间复杂度分析：
最坏的情况即图示的情况，从根一路比较到叶子节点，比较的次数为完全二叉树的高度，即时间复杂度为 O(log₂N)

3.5 堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆

int a[] = {1,5,3,8,7,6};

在这里插入图片描述
【1】向上调整建堆

//向上调整建对堆 --- 0(N*logN)
int n = sizeof(a) / sizeof(a[0]);

for (int i = 1; i < n; i++)
{
	AdjustUp(a, i);
}

【2】向下调整建堆

// 向下要调整建堆 --- O(N) 
int n = sizeof(a) / sizeof(a[0]);
//找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
	AdjustDown(a, n, i);
}

【3】模拟堆插入的过程建堆

// 堆的构建 --- 小堆 O(logN)
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	//模拟堆插入的过程建堆
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	hp->size = 0;
	hp->capacity = n;
	for (int i = 0; i < n; i++)
	{
		HeapPush(hp, a[i]);
	}
}

【向上调整建堆时间复杂度】

在这里插入图片描述

【向下调整建堆时间复杂度】

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

在这里插入图片描述

3.6 堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。
在这里插入图片描述

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->size * 2;
		HPDataType* temp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = temp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size++] = x;

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

3.7 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);

	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	//从父亲的位置开始往下调
	AdjustDown(hp->a, hp->size, 0);
}

3.8 取堆顶的数据

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);

	return hp->a[0];
}

3.9 求堆的数据个数

// 求堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);

	return hp->size;
}

3.10 堆的判空

// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}

四、源代码

4.1 Heap.h文件

#pragma once

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

typedef int HPDataType; //数据元素类型
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap; //堆的结构

//堆的初始化（可要可不要）
void HeapInit(Heap* hp);
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

4.2 Heap.c文件

#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"


// 堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);

	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}

// 堆的构建 --- 小堆
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	hp->size = 0;
	hp->capacity = n;
	for (int i = 0; i < n; i++)
	{
		HeapPush(hp, a[i]);
	}
}

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);

	free(hp->a);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}


//向上调整 --- 插入时使用，保证堆的结构
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while(parent >= 0)
	while (child > 0)
	{
		if (a[child] < a[parent]) //< 改成 > 就是大堆的向上调整
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

// 堆的插入 --- O(logN)
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->size * 2;
		HPDataType* temp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = temp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size++] = x;

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

//向下调整 --- 删除的时候使用
void AdjustDown(HPDataType* a, int size, int parent)
{
	//假设左孩子小
	int child = parent * 2 + 1;
	while (child < size)
	{
		//如果右孩子更小，则将child的下标置为右孩子的下标
		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(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);

	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	//从父亲的位置开始往下调
	AdjustDown(hp->a, hp->size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);

	return hp->a[0];
}
// 求堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);

	return hp->size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}

4.3 Test.c文件

#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"

void Test1()
{
	int a[] = { 4,6,2,1,5,8,2,9 };
	Heap hp;
	int len = sizeof(a) / sizeof(a[0]);
	//HeapInit(&hp);
	模拟堆插入的过程建堆
	//for (int i = 0; i < len; i++)
	//{
	//	HeapPush(&hp, a[i]);
	//}
	HeapCreate(&hp, a, len);

	//打印堆中前k个元素
	/*int k = 4;
	while (k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}*/
	//打印堆
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp)); 
		HeapPop(&hp);
	}
	printf("
");
}

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

今天的分享到此结束，后续将继续向大家带来更多数据结构的小知识！

文章目录

一、堆的概念及介绍

二、结构图示

三、堆的代码实现（图解）

3.1 创建堆结构体即接口

3.2 堆的初始化 && 交换两个数（用于parent 和 child 的交换 ）

3.3 堆的向上调整

3.4 堆向下调整算法（以小堆为例）

3.5 堆的创建

【向上调整建堆时间复杂度】

【向下调整建堆时间复杂度】

3.6 堆的插入

3.7 堆的删除

3.8 取堆顶的数据

3.9 求堆的数据个数

3.10 堆的判空

四、源代码

4.1 Heap.h文件

4.2 Heap.c文件

4.3 Test.c文件

3.2 堆的初始化 && 交换两个数（用于parent 和 child 的交换）