金人三缄网

首页 » 家居用品 » 【数据结构初阶】堆&&堆的实现&&堆排序&&TOP-K

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

2024-04-29 18:04:33 家居用品

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

大家好我是沐曦希💕

文章目录

  • 1.前言
  • 2.堆的概念及结构
    • 2.1 堆的选择题
  • 3.堆的实现
    • 3.1 堆向下调整算法
    • 3.2 堆向上调整算法
    • 3.3 堆的创建
      • 3.3.1 向下调整建堆时间复杂度
      • 3.3.2 向上调整建堆时间复杂度
    • 3.4 堆的插入
    • 3.5 堆的删除
    • 3.6 代码的实现
    • Heap.h
    • test.c
    • Heap.c
  • 4.堆的应用
    • 4.1 堆排序
    • 4.2 TOP-K问题
  • 5.写在最后

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(右孩子) = parent2+2(偶数)
parent = (child - 1)/2

2.1 堆的选择题

1.下列关键字序列为堆的是：（）A 100,60,70,50,32,65B 60,70,65,50,32,100C 65,100,70,32,50,60D 70,65,100,32,50,60E 32,50,100,70,65,60F 50,100,70,65,60,32

在这里插入图片描述
答案是：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
#includevoid 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;}

在这里插入图片描述

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

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

3.2 堆向上调整算法

#includevoid 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;}

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

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

在这里插入图片描述

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

3.6 代码的实现

Heap.h

#pragma once#define _CRT_SECURE_NO_WARNINGS 1#include#include#include#includetypedef 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);

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

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

在这里插入图片描述

4.堆的应用

4.1 堆排序

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

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

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

#includevoid 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;}

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

而不采用小堆：因为根与子树排好了，剩下数据看作堆，父子关系全乱了。只能重新堆剩下数据再一次使用向下调整建堆，选出次小数据，每次时间复杂度为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#includevoid 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;}

在这里插入图片描述

5.写在最后

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

未经允许不得转载：金人三缄网 » 【数据结构初阶】堆&&堆的实现&&堆排序&&TOP-K

相关推荐

商品推荐