• 【数据结构初阶】堆&&堆的实现&&堆排序&&TOP-K

    大家好我是沐曦希💕

    文章目录

    1.前言

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

    在这里插入图片描述

    2.堆的概念及结构

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

    堆的性质：

    • 堆中某个节点的值总是不大于或不小于其父节点的值；
    • 堆总是一棵完全二叉树。
      在这里插入图片描述

    有关堆双亲和孩子数组下标计算公式：
    leftchild(左孩子) = parent2+1(奇数)
    rightchild(右孩子) = parent    2+2(偶数)
    parent = (child - 1)/2

    2.1 堆的选择题

    1.下列关键字序列为堆的是：（）
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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    在这里插入图片描述
    答案是：A

    3.堆的实现

    3.1 堆向下调整算法

    现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
    int array[] = {27,15,19,18,28,34,65,49,25,37};
    在这里插入图片描述

    这里进行小堆的下调

    //要交换两个变量的值，那么要传址调用
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
    //参数a为一维数组的数组名，n是结点的个数，parent是开始下调的节点下标
	int minchild = parent * 2 + 1;
	//假设左孩子比右孩子小，将左孩子下标给minchild
	while (minchild < n)
	//当midchild
	{
		if (a[minchild + 1] < a[minchild] && minchild + 1 < n)
		//判断左孩子和右孩子哪个小，如果左孩子小则跳过，否则minchild++取到右孩子下标
		//这里要判断一下minchild+1是否大于n，从而判定左孩子是否为n-1
		{
			minchild++;
		}
		if (a[minchild] < a[parent])
		//用最小孩子与双亲对比，如果孩子小，则交互孩子与双亲的值
		{
			Swap(&a[minchild], &a[parent]);
			parent = minchild;//将孩子的下标赋值给双亲
			minchild = parent * 2 + 1;
			//求出下一个左孩子的值赋值给minchlid
		}
		else
			break;//当最小孩子不小于父亲时候，则跳出循环
	}
}

    • 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
    #include
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
	int minchild = parent * 2 + 1;
	while (minchild < n)
	{
		if (a[minchild + 1] < a[minchild] && minchild + 1 < n)
		{
			minchild++;
		}
		if (a[minchild] < a[parent])
		{
			Swap(&a[minchild], &a[parent]);
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else
			break;
	}
}
int main()
{
	int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	AdjustDown(arr, sz, 0);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

    • 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

    在这里插入图片描述

    此时任意节点的值总是不小于其父节点的值，即为小堆。

    那么要建大堆则需要通过堆向上调整算法。

    3.2 堆向上调整算法

    #include
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustUp(int* 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;
		}
	}
}
int main()
{
	int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		AdjustUp(arr, i);
	}
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

    • 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

    在这里插入图片描述
    此时任意节点的值总是不大于其父节点的值，即为大堆。

    3.3 堆的创建

    下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
    int a[] = {1,5,3,8,7,6};
    在这里插入图片描述

    每插进一个结点，便调用一次堆向上调整算法或者向下调用调整算法。

    3.3.1 向下调整建堆时间复杂度

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

    因此：向下调整建堆的时间复杂度为O(N)。

    3.3.2 向上调整建堆时间复杂度

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

    3.4 堆的插入

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

    void HeapPush(HP* php, HpDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HpDataType* tmp = (HpDataType*)realloc(php->a, sizeof(HpDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	//调整此时的堆，保持为未插入堆的形态
	AdjustUp(php->a, php->size - 1);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    在这里插入图片描述

    3.5 堆的删除

    删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
    在这里插入图片描述

    堆的删除的用途：得到次大或者次小的数，可以找到前K个大或者小的。

    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);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    3.6 代码的实现

    Heap.h

    #pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
typedef int HpDataType;
typedef struct Heap
{
	HpDataType* a;
	int size;
	int capacity;
}HP;
// 堆的构建
void HeapInit(HP* php);
// 堆的销毁
void HeapDeStory(HP* php);
// 堆的插入
void HeapPush(HP* php, HpDataType x);
// 堆的删除
void HeapPop(HP* php);
// 堆的判空
bool HeapEmpty(HP* php);
// 堆的数据个数
int HeapSize(HP* php);
//打印堆的数据
void HeapPrint(HP* php);
// 取堆顶的数据
HpDataType HeapTop(HP* 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

    test.c

    #include"Heap.h"
int main()
{
	int arr[] = { 15,18,19,25,28,34,65,49,27,37 };
	HP hp;
	HeapInit(&hp);
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		HeapPush(&hp, arr[i]);
	}
	printf("%d\n", HeapTop(&hp));
	HeapPrint(&hp);
	HeapPush(&hp, 10);
	printf("%d\n", HeapTop(&hp));
	HeapPrint(&hp);
	HeapPop(&hp);
	printf("%d\n", HeapTop(&hp));
	HeapPrint(&hp);
	HeapPop(&hp);
	printf("%d\n", HeapTop(&hp));
	HeapPrint(&hp);
	HeapDeStory(&hp);
	return 0;
}

    • 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

    Heap.c

    #include"Heap.h"
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}
void HeapDeStory(HP* php)
{
	assert(php);
	free(php->a);
	php->capacity = 0;
	php->size = 0;
	php->a = NULL;
}
void Swap(HpDataType* pc, HpDataType* pp)
{
	HpDataType tmp = *pc;
	*pc = *pp;
	*pp = tmp;
}
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 = (child - 1) / 2;
		}
		else
			break;
	}
}
void HeapPush(HP* php, HpDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HpDataType* tmp = (HpDataType*)realloc(php->a, sizeof(HpDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	//调整此时的堆，保持为未插入堆的形态
	AdjustUp(php->a, php->size - 1);
}
void AdjustDown(HpDataType* a, int n, int parent)
{
	int minchild = parent * 2 + 1;
	while (minchild < n)
	{
		if (a[minchild + 1] < a[minchild] && minchild + 1 < n)
		{
			minchild++;
		}
		if (a[minchild] < a[parent])
		{
			Swap(&a[minchild], &a[parent]);
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else
			break;
	}
}
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);
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
// 堆的数据个数
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
void HeapPrint(HP* php)
{
	assert(php);
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
HpDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}

    • 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

    在这里插入图片描述

    4.堆的应用

    4.1 堆排序

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

    1. 建堆:
      1.1 升序：建大堆
      1.2 降序：建小堆
    2. 利用堆删除思想来进行排序:
      建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
      在这里插入图片描述

    升序建大堆，然后第一个和最后一个位置交换，把最后一个不看做堆里面的，进行向下调整处理，迭代出最大的，后续依次处理。

    #include
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
/*void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}*/
void AdjustDown(int* a, int n, int parent)
{
	int maxchild = parent * 2 + 1;
	while (maxchild < n)
	{
		if (a[maxchild] < a[maxchild + 1] && maxchild + 1 < n)
		{
			maxchild++;
		}
		if (a[maxchild] > a[parent])
		{
			Swap(&a[maxchild], &a[parent]);
			maxchild = parent;
			parent = (maxchild - 1) / 2;
		}
		else
			break;
	}
}
void HeapSort(int* a, int sz)
{
	int i = 0;
	//建堆--升序建大堆--使用向上调整算法时间复杂度O(N*logN)
	/*for (i = 0; i < sz; i++)
	{
		AdjustUp(a, i);
	}*/
	//建堆--升序建小堆--使用向下调整算法时间复杂度O(N)
	for (i = (sz - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, sz, i);
	}
	for (i = 0; i < sz; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	//选树--O(logN)
	i = 1;
	while (i < sz)
	{
		Swap(&a[0], &a[sz - i]);
		AdjustDown(a, sz - 1, 0);
		i++;
	}
	for (i = 0; i < sz; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
int main()
{
	int arr[] = { 4,5,3,20,17,16 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr, sz);
	return 0;
}

    • 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

    在这里插入图片描述
    建堆时候，升序采用大堆，从倒数第一个非叶子节点(最后一个叶子节点的父亲)开始下调，直到调整到根。因为叶子是没有孩子和它进行上下调整，从倒数第一层开始调整。
    在这里插入图片描述

    而不采用小堆：因为根与子树排好了，剩下数据看作堆，父子关系全乱了。只能重新堆剩下数据再一次使用向下调整建堆，选出次小数据，每次时间复杂度为O(N)，效率低。
    在这里插入图片描述

    4.2 TOP-K问题

    TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
    比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
    对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

    1. 用数据集合中前K个元素来建堆
      1.1 前k个最大的元素，则建小堆
      1.2 前k个最小的元素，则建大堆
    2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素。
      将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
    #include
#include
#include
#include
void CreateDataFile(const char* filename, int N)
{
	assert(filename);
	FILE* fin = fopen(filename, "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		exit(-1);
	}
	int i = 0;
	for (i = 0; i < N; i++)
	{
		fprintf(fin, "%d\n", rand() % 1000);
	}
	fclose(fin);
}
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
	int minChild = parent * 2 + 1;
	while (minChild < n)
	{
		// 找出小的那个孩子
		if (minChild + 1 < n && a[minChild + 1] < a[minChild])
		{
			minChild++;
		}

		if (a[minChild] < a[parent])
		{
			Swap(&a[minChild], &a[parent]);
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void PrintTok(const char* filename, int k)
{
	assert(filename);
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		exit(-1);
	}
	int i = 0;
	int* maxHeap = (int*)malloc(sizeof(int) * k);
	if (maxHeap == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//读取K个数据
	for (i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &maxHeap[i]);
	}
	//K个数建小堆
	for (int j = (k - 2) / 2; j >= 0; --j)
	{
		AdjustDown(maxHeap, k, j);
	}
	int val = 0;
	//继续读取后N-k个
	while (fscanf(fout, "%d", &val) != EOF)
	{
		if (val > maxHeap[0])
		{
			maxHeap[0] = val;
			AdjustDown(maxHeap, k, 0);
		}
	}
	for (i = 0; i < k; i++)
	{
		printf("%d ", maxHeap[i]);
	}
	free(maxHeap);
	maxHeap = NULL;
	fclose(fout);
}
int main()
{
	const char* filename = "Data.txt";
	srand((unsigned int)time(NULL));
	int N = 10000;
	int k = 10;
	//CreateDataFile(filename, N);
	PrintTok(filename, k);
	return 0;
}

    • 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

    在这里插入图片描述

    5.写在最后

    那么堆以及堆应用：堆排序和TOP-K问题就到这里了。
    在这里插入图片描述

  • 相关阅读:
    Word控件Spire.Doc 【文本】教程(16) ；在 Word 中将文本大小写更改为全部大写
    非线性优化问题基本形式概述
    Gif格式图片怎么制作？超简单的方法分享
    JavaScript 的真值与假值 | 如何判断一个对象为空
    Python整理本机Mp3音乐文件
    Python Pandas简介及基础教程+实战示例。
    Pandas教程（非常详细）（第四部分）
    spark的两种groupby，一种不易OOM
    Day14/15/16：哈夫曼树、哈弗曼编码(压缩与解压缩)
    Android Aidl跨进程通讯(三)--进阶使用
  • 原文地址：https://blog.csdn.net/m0_68931081/article/details/126227194