堆结构的深度理解

发布于：2022-11-09 ⋅ 阅读:(152) ⋅ 点赞:(0)

目录

一、堆的概念及其结构

二、堆的实现

2.1 向上调整算法

2.2 向下调整算法

2.3 堆的插入

2.4 堆的删除

2.5 完整实现代码

三、堆排序

3.1 建堆

解决方案一

解决方案二

3.2 建堆时间复杂度分析

方案一分析

方案二分析

3.3 实现排序

3.4 完整代码实现

四、TOP-K问题

思路

本文将详细讲解数据结构中的堆，并非是计算机存储概念上的堆区

一、堆的概念及其结构

概念:

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

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆

性质:
1. 堆中某个节点的值总是不大于或不小于其父节点的值；
2. 堆逻辑结构是一棵完全二叉树，其物理结构为数组

二、堆的实现

2.1 向上调整算法

以小堆为例进行讲解

void AdjustUp(HPDataType* array,int child)
{
	int parent = (child - 1) / 2;
	while (array[child] < array[parent] && child)
	{
		Swap(&array[child], &array[parent]);
		child = parent;
		parent = (child - 1) / 2;
	}
}

2.2 向下调整算法

向下调整算法有一个前提：左右子树必须是堆，才能调整

以小堆为例进行讲解

void AdjustDown(HPDataType* array, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size) {
		if (child + 1 < size && array[child + 1] > array[child]) ++child;
		if (array[child] > array[parent]) {
			Swap(&array[child], &array[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
            break;
        }
	}
}

2.3 堆的插入

先插入数据到数组的尾部，再对插入元素进行向上调整算法，使得插入元素出现在该出现的位置，满足堆的所有性质

void HeapPush(Heap* hp,HPDataType x)
{
	assert(hp);
	if (hp->_size == hp->_capacity) {
		int newCapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
		HPDataType* temp = (HPDataType*)realloc(hp->_data, sizeof(HPDataType) * newCapacity);
		if (temp == NULL) {
			perror("realloc fail:");
			exit(-1);
		}
		hp->_data = temp;
	}
	hp->_data[hp->_size] = x;
	++hp->_size;
	AdjustUp(hp->_data, hp->_size - 1);
}

2.4 堆的删除

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

void HeapPop(Heap* hp)//删除堆顶数据
{
	assert(hp);
	Swap(&(hp->_data[0]), &(hp->_data[hp->_size - 1]));
	--hp->_size;
	AdjustDown(hp->_data, hp->_size, 0);
}

2.5 完整实现代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap {
	HPDataType* _data;
	int _capacity;
	int _size;
}Heap;

void HeapInit(Heap* hp) 
{
	assert(hp);
	hp->_data = NULL;
	hp->_capacity = hp->_size = 0;
}
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_data);
	hp->_capacity = hp->_size = 0;
}

void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType temp = *x;
	*x = *y;
	*y = temp;
}

void AdjustUp(HPDataType* array,int child)
{
	int parent = (child - 1) / 2;
	while (array[child] < array[parent] && child)
	{
		Swap(&array[child], &array[parent]);
		child = parent;
		parent = (child - 1) / 2;
	}
}
void HeapPush(Heap* hp,HPDataType x)
{
	assert(hp);
	if (hp->_size == hp->_capacity) {
		int newCapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
		HPDataType* temp = (HPDataType*)realloc(hp->_data, sizeof(HPDataType) * newCapacity);
		if (temp == NULL) {
			perror("realloc fail:");
			exit(-1);
		}
		hp->_data = temp;
	}
	hp->_data[hp->_size] = x;
	++hp->_size;
	AdjustUp(hp->_data, hp->_size - 1);
}

void AdjustDown(HPDataType* array, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size){
		if (child + 1 < size && array[child + 1] > array[child]) ++child;
		if (array[child] > array[parent]) {
			Swap(&array[child], &array[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
}
void HeapPop(Heap* hp)//删除堆顶数据
{
	assert(hp);
	Swap(&(hp->_data[0]), &(hp->_data[hp->_size - 1]));
	--hp->_size;
	AdjustDown(hp->_data, hp->_size, 0);
}

HPDataType HeapTop(Heap* hp) 
{
	assert(hp);
	assert(hp->_size > 0);
	return (hp->_data[0]);
}
bool HeapIsEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}

三、堆排序

3.1 建堆

若要排升序，则要建大堆；若要排降序，则要建小堆

建堆问题有两种解决方案，其中解决方案二更好

解决方案一

利用堆插入的思想，尾部每多一个元素则进行一次向上调整

for (int i = 1; i < size; ++i) {
	AdjustUp(array, i);
}

解决方案二

向下调整算法的前提为左右子树必须是堆才可以进行调整。

若想建堆，可以从倒数的第一个非叶子节点的子树开始调整(使用向下调整算法)，一直调整到根节点，就可以将整棵调整成堆

for (int i = (size - 1 - 1) / 2; i >= 0; --i) {//叶子不需要调整
		AdjustDown(array, size, i);
}

3.2 建堆时间复杂度分析

堆是完全二叉树，而满二叉树也是特殊的完全二叉树，此处为了简化使用满二叉树来证明

(时间复杂度本身就是分析近似值的，稍多几个节点并不影响最终结果)

方案一分析

 由上可知，方案一的时间复杂度为O(NlogN)

方案二分析

 由上可知，方案二的时间复杂度为O(N)

3.3 实现排序

利用删除的思想，每次"删除"堆顶的元素(若为小堆即最小值，若为大堆即最大值)

但并非真正删除，而是在逻辑中的堆进行删除，放在堆的最后一个位置，下次计算时不再将该元素视为在堆中。

for (int i = size- 1; i > 0; --i)//删除的思想，每次删除的都是堆中最小的数
{
	Swap(&array[0], &array[i]);
	AdjustDown(array, i, 0);
}

3.4 完整代码实现

#include<stdio.h>
typedef int HPDataType;
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType temp = *x;
	*x = *y;
	*y = temp;
}
void AdjustDown(HPDataType* array, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size) {
		if (child + 1 < size && array[child + 1] > array[child]) ++child;
		if (array[child] > array[parent]) {
			Swap(&array[child], &array[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
}
void HeapSort(int* array,int size) 
{
	for (int i = (size - 1 - 1) / 2; i >= 0; --i) {//叶子不需要调整
		AdjustDown(array, size, i);
	}
	for (int i = size- 1; i > 0; --i)//删除的思想，每次删除的都是堆中最小的数
	{
		Swap(&array[0], &array[i]);
		AdjustDown(array, i, 0);
	}
}
int main()
{
	int array[] = { 27,15,19,18,28,34,65,49,25,37 };
	HeapSort(array, sizeof(array) / sizeof(array[0]));
	for (int i = 0; i < sizeof(array) / sizeof(array[0]); ++i) {
		printf("%d ", array[i]);
	}
	return 0;
}

四、TOP-K问题

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

对于Top-K问题，能想到的最简单直接的方式就是排序

但是若数据量非常大，排序就不太可取了(因为内存大小有限，数据不能一下全部加载到内存中)

最佳的方式就是用堆来解决

思路

1.用数据集合中前K个元素来建堆
        若求前k个最大的元素，则建小堆
        若求前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素
 

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
typedef int HPDataType;
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType temp = *x;
	*x = *y;
	*y = temp;
}
void AdjustDown(HPDataType* array, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size) {
		if (child + 1 < size && array[child + 1] > array[child]) ++child;
		if (array[child] > array[parent]) {
			Swap(&array[child], &array[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
}
void PrintTopK(int* array, int n, int k)
{
	int* MinHeap = (int*)malloc(sizeof(int) * k);
	if (MinHeap == NULL) {
		perror("malloc fail:");
		exit(-1);
	}

	for (int i = 0; i < k; ++i) {//取前k个数据
		MinHeap[i] = array[i];
	}

	for (int i = (k - 1 - 1) / 2; i >= 0; --i) {//建堆
		AdjustDown(MinHeap, k, i);
	}
	for (int i = k; i < n; ++i) {//用剩余的N-K个元素依次与堆顶元素来比较
		if (array[i] > MinHeap[0]) {
			Swap(&array[i], &MinHeap[0]);
			AdjustDown(MinHeap, k, 0);
		}
	}

	for (int i = 0; i < k; ++i) {//输出
		printf("%d ", MinHeap[i]);
	}
	printf("\n");
}
int main()
{
	int n = 10000;
	int* array = (int*)malloc(sizeof(int) * n);
	if (array == NULL) {
		perror("malloc fail:");
		exit(-1);
	}

	srand((unsigned)time(NULL));
	for (size_t i = 0; i < n; ++i)
	{
		array[i] = rand() % 1000000;
	}

	array[5] = 1000000 + 1;
	array[1231] = 1000000 + 2;
	array[531] = 1000000 + 3;
	array[5121] = 1000000 + 4;
	array[115] = 1000000 + 5;
	array[2335] = 1000000 + 6;
	array[9999] = 1000000 + 7;
	array[76] = 1000000 + 8;
	array[423] = 1000000 + 9;
	array[3144] = 1000000 + 10;

	PrintTopK(array, n, 10);//k == 10
	return 0;
}

本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布