数据结构从入门到精通—

堆

前言
一、二叉树的顺序结构及实现 (堆）
- 1.1二叉树的顺序结构
- 1.2堆的概念及结构
二、堆的练习题
- 答案
三、堆的实现
- 3.1堆向下调整算法
- 3.2堆的创建
- 3.3建堆时间复杂度
- 3.4堆的插入
- 3.5堆的删除
- 3.6堆的代码实现
四、堆的具体实现代码
- Heap.h
- Heap.c
- Test.c
- 堆的初始化
- 堆的销毁
- 数据交换函数
- 堆的向上交换
- 元素入堆
- 堆的向下交换
- 元素出堆
- 堆顶元素
- 堆是否为空
五、堆的应用
- 5.1 数组向上调整建堆
- 5.2数组向下调整建堆
- 5.3堆排序
- 5.4TOP-K问题
- - 直接建数据
  - 文件建数据
  - 完整代码
  - - test.c
    - 数据交换
    - 向下调整
    - 主函数

前言

堆是一种特殊的树形数据结构，具有完全二叉树的特性。在堆中，父节点的值总是大于或等于（大顶堆）或小于或等于（小顶堆）其子节点的值。堆通常用于实现优先队列，其中每个元素都有一个优先级，优先级最高的元素总是位于堆的根节点。堆的插入和删除操作的时间复杂度都是O(log n)，因此堆是一种高效的数据结构。此外，堆还可以用于实现内存管理，例如垃圾回收和内存分配等。

一、二叉树的顺序结构及实现 (堆）

1.1二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
在这里插入图片描述

1.2堆的概念及结构

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

堆的性质：

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

在这里插入图片描述

二、堆的练习题

下列关键字序列为堆的是：（）
A、 100,60,70,50,32,65
B 、60,70,65,50,32,100
C、 65,100,70,32,50,60
D、 70,65,100,32,50,60
E、 32,50,100,70,65,60
F 、50,100,70,65,60,32
已知小根堆为8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（）。
A 、1
B、 2
C 、3
D 、4
一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为
A、(11 5 7 2 3 17)
B、(11 5 7 2 17 3)
C、(17 11 7 2 3 5)
D、(17 11 7 5 3 2)
E、(17 7 11 3 5 2)
F、(17 7 11 3 2 5)
最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是（）
A、[3，2，5，7，4，6，8]
B、[2，3，5，7，4，6，8]
C、[2，3，4，5，7，8，6]
D、[2，3，4，5，6，7，8]

答案

1.A
2.C
3.C
4.C

三、堆的实现

3.1堆向下调整算法

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

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

在这里插入图片描述

3.2堆的创建

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

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

在这里插入图片描述

3.3建堆时间复杂度

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

在这里插入图片描述
因此：建堆的时间复杂度为O(N)。

3.4堆的插入

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

在这里插入图片描述

3.5堆的删除

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

在这里插入图片描述

3.6堆的代码实现

typedef int HPDataType;
typedef struct Heap
{
 	HPDataType* _a;
 	int _size;
 	int _capacity; 
}Heap;
 
// 堆的构建
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);

四、堆的具体实现代码

Heap.h

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

typedef int HPDataType;

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

void Swap(HPDataType* a, HPDataType* b);//数据交换函数
void AdjustUp(HPDataType* a, int child);//向上交换
void AdjustDown(HPDataType* a, int n,int parent);//向下交换
//堆的初始化
void HPInit(HP* php);
//堆的销毁
void HPDestroy(HP* php);

//插入数据
void HPPush(HP* php,HPDataType x);

HPDataType HPTop(HP* php);//堆顶元素
//删除堆顶元素
void HPPop(HP* php);
bool HPEmpty(HP* php);

Heap.c

#include "Heap.h"
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity =  php->size = 0;
}
void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType temp = *a;
	*a = *b;
	*b = temp;
}
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		size_t newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* newnode = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
		if (newnode == NULL)
		{
			perror("newnode realloc : ");
			return;
		}
		php->a = newnode;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);
}
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HPPop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}
void AdjustDown(HPDataType* 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[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
HPDataType HPTop(HP* php)
{
	assert(php);
	return php->a[0];
}
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

Test.c

#include"Heap.h"

int main()
{
	//int a[] = { 50,100,70,65,60,32 };
	int a[] = { 60,70,65,50,32,100 };

	HP hp;
	HPInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}

	printf("%d\n", HPTop(&hp));
	HPPop(&hp);
	printf("%d\n", HPTop(&hp));
	while (!HPEmpty(&hp))
	{
		printf("%d\n", HPTop(&hp));
		HPPop(&hp);
	}

	HPDestroy(&hp);

	return 0;
}

堆的初始化

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

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

堆是一种特殊的树形数据结构，通常用于实现优先队列。在初始化堆时，需要按照一定规则将元素填充到堆中。一般来说，堆的初始化可以采用从上到下、从左到右的方式遍历数组，对于每个非叶子节点，将其与其子节点中较大的一个进行交换，确保父节点的值不小于其子节点的值，从而满足堆的性质。这种操作被称为堆化或调整。通过遍历整个数组并进行堆化操作，最终可以得到一个满足堆性质的堆结构。

堆的销毁

//堆的销毁
void HPDestroy(HP* php);

void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

堆的销毁是释放由堆分配的内存空间的过程。当不再需要堆上分配的对象时，必须显式地销毁它们以释放内存，防止内存泄漏。销毁操作通常通过调用对象的析构函数来完成，它会执行必要的清理任务，如释放对象拥有的资源。销毁后，对象变得无效，不应再被使用。在C++中，可以使用delete操作符来销毁堆上分配的对象。在销毁过程中，需要特别注意避免重复销毁和野指针问题。

数据交换函数

void Swap(HPDataType* a, HPDataType* b);//数据交换函数

void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType temp = *a;
	*a = *b;
	*b = temp;
}

堆的向上交换

void AdjustUp(HPDataType* a, int child);//向上交换

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

堆的向上交换是在堆排序算法中常用的一个操作。在堆排序过程中，当某个节点的值大于其父节点时，需要进行向上交换，即将该节点与其父节点交换位置，以保持堆的性质。这种交换操作从下往上进行，直至满足堆的定义要求。向上交换是堆排序中调整堆结构的关键步骤之一，有助于提高排序效率。

元素入堆

//插入数据
void HPPush(HP* php,HPDataType x);

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		size_t newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* newnode = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
		if (newnode == NULL)
		{
			perror("newnode realloc : ");
			return;
		}
		php->a = newnode;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);
}

元素入堆是指将一个元素插入到堆（Heap）这种数据结构中的过程。堆通常是一种特殊的树形数据结构，其每个父节点的值都大于或等于（在最大堆中）或小于或等于（在最小堆中）其子节点的值。元素入堆的过程通常涉及到调整堆的结构，以保持其性质。在插入新元素后，可能需要通过“上浮”或“下沉”操作来调整元素位置，确保堆的性质得以维持。这个过程对于堆排序、优先队列等算法至关重要。

堆的向下交换

void AdjustDown(HPDataType* a, int n,int parent);//向下交换

void AdjustDown(HPDataType* 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[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

堆的向下交换是堆排序算法中的一个重要步骤。在堆排序中，首先构建一个最大堆或最小堆，然后通过不断将堆顶元素与堆尾元素交换并重新调整堆结构，达到排序的目的。向下交换是指将堆顶元素与其子节点中较大的（对于最大堆）或较小的（对于最小堆）元素交换位置，然后重新调整子堆，以保持堆的性质。这个过程重复进行，直到整个堆排序完成。向下交换是堆排序算法中的关键步骤，能够确保堆的性质得以维持，从而实现快速排序。

元素出堆

void HPPop(HP* php);

void HPPop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

出堆操作是堆数据结构中的一种常见操作，主要用于从堆中移除并返回堆顶元素（即具有最大或最小值的元素）。在执行出堆操作时，首先需要将堆顶元素与堆的最后一个元素交换位置，然后调整剩余元素以维持堆的性质。对于最大堆，堆顶元素总是最大的，而对于最小堆，堆顶元素总是最小的。出堆操作的时间复杂度通常为O(log n)，其中n是堆中元素的数量。通过出堆操作，可以高效地获取并删除堆中的最大或最小元素，从而在各种算法和数据结构中实现高效的数据处理和查询。

堆顶元素

HPDataType HPTop(HP* php);//堆顶元素

HPDataType HPTop(HP* php)
{
	assert(php);
	return php->a[0];
}

堆是否为空

bool HPEmpty(HP* php);

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

五、堆的应用

5.1 数组向上调整建堆

void HPInitArray(HP* php, HPDataType* a, int n)

void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("php->a malloc :");
		return;
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->capacity = php->size = n;
	//向上排序 时间复杂度N*log N
	for (int i = 1; i < php->size; i++)
	{
		AdjustUp(php->a, i);
	}
}

数组向上调整建堆是一种构建堆（Heap）的方法，通常用于实现堆排序算法。该方法从数组的中间位置开始，将每个元素作为潜在的堆顶，然后通过向上调整操作，确保以该元素为根的子树满足堆的性质（最大堆或最小堆）。向上调整操作包括将根节点与其子节点比较，并在必要时交换它们的位置，以确保堆的性质得以维持。通过从数组的中间位置到第一个元素的顺序进行向下调整，最终可以构建出一个完整的堆结构。这种方法的时间复杂度为O(nlogn)，其中n是数组的长度。
在这里插入图片描述

在这里插入图片描述

5.2数组向下调整建堆

void HPInitArray(HP* php, HPDataType* a, int n)

void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("php->a malloc :");
		return;
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->capacity = php->size = n;
	向上排序 时间复杂度N*log N
	//for (int i = 1; i < php->size; i++)
	//{
	//	AdjustUp(php->a, i);
	//}
	//向下排序,时间复杂度N
	for (int i = (php->size - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
}

数组向下调整建堆是指在构建一个最大堆（或最小堆）时，从数组末尾开始，逐个向上调整每个非叶子节点，使其满足堆的性质。具体步骤如下：

从最后一个非叶子节点开始，向前遍历数组。
对于每个节点，检查其是否满足堆的性质，即是否大于（或小于）其子节点。
如果不满足堆的性质，则将其与其较大的子节点交换位置，并继续向下调整子树，直到满足堆的性质。
重复步骤2和3，直到遍历完所有节点。

通过这种向下调整的方式，可以高效地构建一个最大堆（或最小堆），为后续的堆排序等操作提供基础。这种办法的时间复杂度是O(N).
在这里插入图片描述

5.3堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

建堆
- 升序：建大堆
- 降序：建小堆
利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

在这里插入图片描述

void HeapSort(HPDataType* a, int n)
{
	for (int i = (n-1 - 1)/2; i >=0 ; i--)
	{
		AdjustDown(a,n,i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

堆排序是一种基于二叉堆数据结构的排序算法。它首先将待排序序列构造成一个大顶堆（或小顶堆），然后依次将堆顶元素（最大值或最小值）与堆尾元素交换并删除，再通过调整堆结构使其保持为堆，重复此过程直至堆为空。这样，就能得到一个有序序列。堆排序的时间复杂度O(nlogn)，空间复杂度为O(1)。

5.4TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

用数据集合中前K个元素来建堆
- 前k个最大的元素，则建小堆
- 前k个最小的元素，则建大堆
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
ps：剩余的数据可能是非递增的，想要递增的话，可以自己添加排序算法

直接建数据

void PrintTopK(int* a, int n, int k)
{
 // 1. 建堆--用a中前k个元素建堆
 
 // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
}
 
void TestTopk()
{
 	int n = 10000;
 	int* a = (int*)malloc(sizeof(int)*n);
 	srand(time(0));
 	for (size_t i = 0; i < n; ++i)
	 {
 		a[i] = rand() % 1000000;
 	}
	a[5] = 1000000 + 1;
 	a[1231] = 1000000 + 2;
 	a[531] = 1000000 + 3;
 	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
 	a[2335] = 1000000 + 6;
 	a[9999] = 1000000 + 7;
 	a[76] = 1000000 + 8;
 	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
 	PrintTopK(a, n, 10);
}

文件建数据

void CreateNDate()
{
	int k = 10000;
	srand((unsigned int)time(NULL));
	FILE* pf = fopen("data.txt", "w");
	if (pf == NULL)
	{
		perror("pf fopen :");
		return;
	}
	for (int i = 0; i < k; i++)
	{
		fprintf(pf, "%d\n", rand()%10000 + i );
	}
	fclose(pf);
}

完整代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
void CreateNDate()
{
	int k = 10000;
	srand((unsigned int)time(NULL));
	FILE* pf = fopen("data.txt", "w");
	if (pf == NULL)
	{
		perror("pf fopen :");
		return;
	}
	for (int i = 0; i < k; i++)
	{
		fprintf(pf, "%d\n", rand()%10000 + i );
	}
	fclose(pf);
}
void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
void AdjustDown(int* a, int n, int parent)
{
	assert(a);
	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[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
int main()
{
	//CreateNDate();
	int k = 0;
	printf("输入需要排序的个数:  \n", &k);
	scanf("%d", &k);
	int* a = (int*)malloc(sizeof(int) * k);
	FILE* pf = fopen("data.txt", "r");
	if (pf == NULL)
	{
		perror("pf fopen :");
		return;
	}
	for (int i = 0; i < k; i++)
	{
		fscanf(pf, "%d", &a[i]);
	}
	for (int i = (k - 1 - 1) / 2 ; i >= 0; i--)
	{
		AdjustDown(a, k, i);
	}
	int x = 0;
	while (fscanf(pf, "%d", &x) != EOF)
	{
		if (a[0] < x)
		{
			a[0] = x;
			AdjustDown(a, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", a[i]);
	}

	fclose(pf);
	return 0;
}

数据交换

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

向下调整

void AdjustDown(int* a, int n, int parent)
{
	assert(a);
	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[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

主函数

int main()
{
	//CreateNDate();  在需要新数据的时候开启或关闭
	int k = 0;
	printf("输入需要排序的个数:  \n", &k);
	scanf("%d", &k);
	int* a = (int*)malloc(sizeof(int) * k);
	FILE* pf = fopen("data.txt", "r");
	if (pf == NULL)
	{
		perror("pf fopen :");
		return;
	}
	for (int i = 0; i < k; i++)
	{
		fscanf(pf, "%d", &a[i]);
	}
	for (int i = (k - 1 - 1) / 2 ; i >= 0; i--)
	{
		AdjustDown(a, k, i);
	}
	int x = 0;
	while (fscanf(pf, "%d", &x) != EOF)
	{
		if (a[0] < x)
		{
			a[0] = x;
			AdjustDown(a, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", a[i]);
	}

	fclose(pf);
	return 0;
}