堆的实现

「这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战」

💦 堆的实现

1、堆向下调整算法

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

    ❗ 建堆 ❕

        有一个随机值的数组，把它理解成完全二叉树，并模拟成堆 (大堆/小堆)

    ——————————————————-Cut———————————————————

c复制代码int array[] = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37}

    ❓ 观察上面这组数据 ❔

        根下面的左右子树都是小根堆，其实堆向下调整算法就是针对这种特殊数据结构

    ——————————————————-Cut———————————————————

    ❓ 针对于这种类型的数据应该怎么调堆 ❔

       思路：从根开始与左右孩子比较，如果孩子比父亲小，则两两交换位置，再继续往下调，直到左右孩子都比父亲大或者调到叶子具体见下图：

    ——————————————————-Cut———————————————————

    ❓ 如果不满足左右子树是堆，怎么调整 ❔

c复制代码int array[] = {27, 37, 28, 18, 19, 34, 65, 25, 49, 15}

    根的左右子树 37、28 都不满足：这里的想法就是先让左右子树先满足；而对于左右子树 37、28 来说又需要让 37 先满足；这样依此类推直至满足堆的条件。那干脆就从倒数的第一棵树，也就是倒数的第一个非叶子节点开始调整

2、堆的创建

    ❗ 这里从倒数的第一个非叶子节点开始调整 ❕

c复制代码#include<stdio.h>

//实现父子交换的函数
void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
//实现调整
void AdjustDown(int* arr, int sz, int parent)
{
	//确定左孩子的下标
	int child = parent * 2 + 1;
	//孩子的下标超出数组的范围就停止
	while (child < sz)
	{
		//确定左右孩子中较小/大的那个
			//左孩子大于右孩子，所以让child记录较小孩子的下标 || (arr[child]<arr[child+1]记录较大孩子的下标)
		if (arr[child] > arr[child + 1] && child + 1 < sz)
		{
			child++; //(当只有一个左孩子时，会越界，且后面使用时会发生非法访问)
		}
		//判断父亲和小孩子
			//小孩子小于父亲，则交换，且继续调整 || (arr[child]>arr[parent]大孩子大于父亲，则交换，且继续调整)
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			//迭代
			parent = child;
			//重新确定左孩子的下标(当最后的叶子节点是parent时，这时去确定child会以读的方式越界，但可以不关心)
			child = parent * 2 + 1;
		}
		//小孩子大于父亲，则停止调整
		else
		{
			break;
		}
	}
}
//堆排序 -> 效率更高
void HeapSort(int* arr, int sz)
{
	//建堆
	int i = 0;
	//从最后一棵树开始调整，也就是最后一个节点的父亲
	for (i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, sz, i);
	}
}
int main()
{
	//左右子树都为堆
	int arr1[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	//左右子树都为非堆
	int arr2[] = { 27, 37, 28, 18, 19, 34, 65, 25, 49, 15 };

	HeapSort(arr1, sizeof(arr1) / sizeof(arr1[0]));
	int i = 0;
	for (i = 0; i < sizeof(arr1) / sizeof(arr1[0]); i++)
	{
		printf("%d ", arr1[i]);
	}

	printf("\n");

	HeapSort(arr2, sizeof(arr2) / sizeof(arr2[0]));
	for (i = 0; i < sizeof(arr2) / sizeof(arr2[0]); i++)
	{
		printf("%d ", arr2[i]);
	}
	return 0;
}

    💨 输出结果：

      小堆

      大堆

3、堆的时间复杂度

      ❓ 证明建堆的时间复杂度是O(N) ❔

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

建堆的调用次数用 T(N) 表示：(从最后一个非叶子节点 <也就是倒数第二层> 开始，最坏的情况下：倒数第二层每个节点最多能向下调 1 次；倒数第三层每个节点最多能向下调 2 次；倒数第四层每个节点最多能向下调 3 次；)

每层节点个数 ×\times× 最坏情况向下调整次数：

T(N) = 2^h-2^ ×\times× 1 + 2^h-3^ ×\times× 2 + … … + 2^0^ ×\times× (h-1)

这里我们从上至下开始

T(N) = 2^0^ ×\times× (h - 1) + 2^1^ ×\times× (h - 2) + 2^2^ ×\times× (h - 3) + 2^3^ ×\times× (h - 4) + … … + 2^h-3^ ×\times× 2 + 2^h-2^ ×\times× 1

    ❗ 错位相减法 ❕

      等号左右两边乘个 2 得到一个新公式，再用新公式减去旧的公式，具体见下图

4、堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

5、堆的删除

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

6、堆的代码实现

⚠ 注意 ⚠

    ▶ 堆的初始化一般是使用数组进行初始化的

    ▶ 堆的插入数据不分头插、尾插，将数据插入后，原来堆的属性不变

      先放在数组的最后一个位置，再向上调整

    ▶ 堆的删除数据删除的是堆顶的数据，将数据删除后，原来堆的属性不变

      为了效率，将第一个和最后一个元素交换，再减容，然后再调整

❗ 这里需要三个文件 ❕

    1️⃣ Heap.h，用于函数的声明

c复制代码#pragma once

//头
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

typedef int HPDataType;

//C++ -> priority_queue 在C++里用的是优先级队列，其底层就是一个堆
//大堆
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
//函数的声明
//交换
void Swap(int* px, int* py);
//向下调整
void AdjustDown(int* arr, int n, int parent);
//向上调整
void AdjustUp(int* a, int child);
//使用数组进行初始化
void HeapInit(HP* php, HPDataType* a, int n);
//回收空间
void HeapDestroy(HP* php);
//插入x，保持它继续是堆
void HeapPush(HP* php, HPDataType x); 
//删除堆顶的数据，保持它继续是堆
void HeapPop(HP* php);
//获取堆顶的数据，也就是最值
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);
//堆的数据个数
int HeapSize(HP* php);
//输出
void HeapPrint(HP* php);

    2️⃣ Heap.c，用于函数的定义

c复制代码#include"Heap.h"


void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void AdjustDown(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (arr[child] < arr[child + 1] && child + 1 < n)
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void AdjustUp(int* a, int child)
{
	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 HeapPrint(HP* php)
{
	assert(php);

	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
//1、对于HeapCreate函数，结构体不是外面传进来的，而是在函数内部自己malloc空间，再创建的
/* 
HP* HeapCreate(HPDataType* a, int n)
{}
*/
//2、对于HeapInit函数，在外面定义一个结构体，把结构体的地址传进来
void HeapInit(HP* php, HPDataType* a, int n)
{
	assert(php); 
	//malloc空间(当前数组大小一样的空间)
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//使用数组初始化
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = n;
	php->capacity = n;
	//建堆 
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, n, i);
	}
}
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	//空间不够，增容
	if (php->size == php->capacity)
	{
		HPDataType* temp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
		if (temp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			php->a = temp;	
		}
		php->capacity *= 2;
	}
	//将x放在最后
	php->a[php->size] = x;
	php->size++;
	//向上调整
	AdjustUp(php->a, php->size - 1);
}
void HeapPop(HP* php)
{
	assert(php);
	//没有数据删除就报错
	assert(!HeapEmpty(php));
	//交换首尾
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;
	//向下调整
	AdjustDown(php->a, php->size, 0);
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	//没有数据获取就报错
	assert(!HeapEmpty(php));
	
	return php->a[0];
}
int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

    3️⃣ Test.c，用于测试函数

c复制代码#include"Heap.h"

void TestHeap()
{
	int arr[] = { 27, 37, 28, 18, 19, 34, 65, 25, 49, 15 };
	HP hp;
	HeapInit(&hp, arr, sizeof(arr)/sizeof(arr[0]));
	HeapPrint(&hp);
	HeapPush(&hp, 18);
	HeapPrint(&hp);
	HeapPush(&hp, 98);
	HeapPrint(&hp);
	printf("\n\n");
	//将堆这数据结构实现好后，我们就可以利用这些接口实现排序
	while(!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));	
		HeapPop(&hp);
	}
	printf("\n");
	
}
int main()
{
	TestHeap();
	return 0;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有