投稿
  1. 首页
  2. C

[数据结构]

code • 2022-4-18 • C • 阅读 42

[数据结构],第1张

前置知识：👉[数据结构](7)什么是树

文章目录
  • 什么是堆
  • 堆的实现（小堆）
    • 初始化和销毁
    • 调整算法
      • 向上调整
      • 向下调整
    • 插入
    • 删除
    • 打印 判空 大小 返回堆顶元素
    • 完整代码
  • 堆排序
    • 对数组建堆
    • 排序
  • Top-K问题
  • 总结

什么是堆
  • 堆（Heap）就是一棵完全二叉树，通常使用数组实现。

  • 堆中某个结点的值总是不大于或不小于其父结点的值
  • 父结点大于等于子结点的叫大堆（或大根堆，大顶堆），父结点小于等于子结点的叫小堆（或小根堆，小顶堆）

注意：

  • 这里的堆和 *** 作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是 *** 作系统中管理内存的一块区域分段。

  • 堆的左右孩子结点之间没有直接的大小关系。

    所以它的数组不一定是有序的。

堆的实现（小堆）

结构就按顺序表的来。

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;
初始化和销毁 
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
调整算法

要保证插入删除数据后还是个堆，就需要进行一定的调整。

这种调整有两种方法。

向上调整
  • 比较要调整的数据与其父亲结点的大小，如果它比父亲小，那么就交换。

    大堆反之

  • 重复上一步直到父亲比它小，或者它成为根结点。

二叉树在数组中怎么找父结点和孩子结点的方法在上一篇中已经讲过：

将 n n n个结点的完全二叉树按从上至下，从左至右的顺序存入数组。

  • 下标为 i ( i > 0 ) i(i>0) i(i>0)的结点，其父结点的下标为 ( i − 1 ) / 2 (i-1)/2 (i−1)/2，下标 i = 0 i=0 i=0的是根结点，没有父结点。

  • 下标为 i i i的结点，其左孩子的下标为 2 ∗ i + 1 2*i+1 2∗i+1，右孩子的下标为 2 ∗ i + 2 2*i+2 2∗i+2，若计算结果大于 n − 1 n-1 n−1则说明没有该孩子结点。

void Swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void AdjustUp(HPDataType* a, size_t child)
{
	size_t 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;
		}
	}
}
向下调整
  • 找到要调整的结点的孩子结点，选出其中小的那个
  • 如果这个孩子比它小，则交换
  • 重复上面两步，直到它的孩子比它大或者它成为叶子节点。

这里比向上调整要多传一个参数size，因为向上调整可能调到根结点，也就是下标为0的时候结束，

而向下调整可能调到最后一个结点，需要知道数组的大小。

void AdjustDown(HPDataType* a, size_t size, size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		// 1、选出左右孩子中小的那个
		if (child + 1 < size && a[child + 1] > a[child]) //注意确定有没有右孩子
		{
			++child;
		}

		// 2、如果孩子小于父亲，则交换，并继续往下调整
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

那么这种算法的时间复杂度是多少？

最坏的情况就是从最顶层调到最底层或者最底层调到最顶层。

有多少层就执行多少次

所以时间复杂度就是 O ( log ⁡ n ) O(\log n) O(logn)

插入

因为物理结构是数组，所以最优的插入方式就是尾插，然后再用向上调整算法进行调整即可。

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//如果满了就扩容
	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType)* newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}
    //插到尾部
	php->a[php->size] = x;
	++php->size;

	// 向上调整，控制保持是一个小堆
	AdjustUp(php->a, php->size - 1);
}
删除

堆的删除其实就是删除根结点。

从数组的角度来看，我们只要把首元素和最后一个元素交换，然后size--即可

然后对新的首元素，也就是根节点进行向下调整即可。

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	Swap(&php->a[0], &php->a[php->size - 1]);
	--php->size;

	AdjustDown(php->a, php->size, 0);
}
打印 判空 大小 返回堆顶元素 
void HeapPrint(HP* php)
{
	assert(php);
	for (size_t i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

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

size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
完整代码

头文件Heap.h

#pragma once
#include
#include
#include
#include

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

void Swap(HPDataType* pa, HPDataType* pb);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPrint(HP* php);

void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
bool HeapEmpty(HP* php);
size_t HeapSize(HP* php);
HPDataType HeapTop(HP* php);

函数实现

#include "Heap.h"
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

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

void Swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void AdjustUp(HPDataType* a, size_t child)
{
	size_t 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 AdjustDown(HPDataType* a, size_t size, size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		// 1、选出左右孩子中小的那个
		if (child + 1 < size && a[child + 1] < a[child]) //注意确定有没有右孩子 //大堆就把右边的 < 换成 >
		{
			++child;
		}

		// 2、如果孩子小于父亲，则交换，并继续往下调整
		if (a[child] < a[parent]) //大堆把 < 换成 >
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//如果满了就扩容
	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}
	//插到尾部
	php->a[php->size] = x;
	++php->size;

	// 向上调整，控制保持是一个小堆
	AdjustUp(php->a, php->size - 1);
}

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	Swap(&php->a[0], &php->a[php->size - 1]);
	--php->size;

	AdjustDown(php->a, php->size, 0);
}

void HeapPrint(HP* php)
{
	assert(php);
	for (size_t i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

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

size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
堆排序

顾名思义，就是利用堆来排序。

因为堆顶总是最小/大的元素。

一个很容易想到的方法就是 取堆顶元素，然后pop，如此反复。

比如要实现升序，那么就建一个小堆，依次取出最小的，次小的，次次小的  ⁣ ⋯  ⁣ ⋯ \dotsi\dotsi ⋯⋯

void HeapSort(int* a, int n)
{
	//建堆，插入
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < n; ++i)
	{
		HeapPush(&hp, a[i]);
	}
	//取出
	size_t j = 0;
	while (!HeapEmpty(&hp))
	{
		a[j++] = HeapTop(&hp);
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}

优化：

上面的方法是在实现了堆的前提下写出来的，而且还使用了额外空间，十分麻烦。

能不能写一个空间复杂度为 O ( 1 ) O(1) O(1)方法呢？

其实可以直接在原数组上建堆。

对数组建堆

有两种方法

1. 向上调整

向上调整一般是对最后一个元素调，但是这个元素之前的元素必须是一个堆。

那么可以先把数组前两个元素看成一个堆，对第二个元素向上调整，再把前三个都看成一个堆，对第三个向上调整  ⁣ ⋯  ⁣ ⋯ \dotsi\dotsi ⋯⋯

void HeapSort(int* a, int n)
{
	for (int i = 1; i < n; ++i)
	{
		AdjustUp(a, i);
	}
    
    //...
}

时间复杂度计算：

假设最坏的情况，从第二个元素开始每个都要向上调整，第 k k k层每个元素都要调整 k − 1 k-1 k−1次，第 k k k层有 2 k − 1 2^{k-1} 2k−1个元素。

那么总的建堆调整次数为：

T ( h ) = 2 1 × 1 + 2 2 × 2 + 2 3 × 3 +  ⁣ ⋯ + 2 h − 1 × ( h − 1 )   ① T(h)=2^1\times1+2^2\times2+2^3\times3+\dotsi+2^{h-1}\times(h-1)\space① T(h)=21×1+22×2+23×3+⋯+2h−1×(h−1) ①

等式两边同时乘2

2 T ( h ) = 2 2 × 1 + 2 3 × 2 + 2 4 × 3 +  ⁣ ⋯ + 2 h × ( h − 1 )   ② 2T(h)=2^2\times1+2^3\times2+2^4\times3+\dotsi+2^h\times(h-1)\space② 2T(h)=22×1+23×2+24×3+⋯+2h×(h−1) ②

② − ① ②-① ②−①，错位相减

T ( h ) = − ( 2 + 2 2 + 2 3 + 2 h − 1 ) + 2 h ( h − 1 ) = 2 h ( h − 2 ) + 2 T(h)=-(2+2^2+2^3+2^{h-1})+2^h(h-1)=2^h(h-2)+2 T(h)=−(2+22+23+2h−1)+2h(h−1)=2h(h−2)+2

又 h = log ⁡ 2 ( n + 1 ) h=\log_2(n+1) h=log2​(n+1)

代入，取最高项，化简得

时间复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)

2. 向下调整

向下调整一般是对第一个元素调，但是它的左子树和右子树必须满足堆。

所以和向上调整反过来，从后往前调。

注意到叶子节点不用调整，而最后一个非叶子结点就是最后一个结点的父结点。

void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	//...
}

时间复杂度计算：

叶子结点不用调，也就是从倒数第二层开始，第 k k k层每个元素调 h − k h-k h−k次，第 k k k层有 2 k − 1 2^{k-1} 2k−1个结点

那么总的建堆调整次数为：

T ( h ) = 2 h − 2 × 1 + 2 h − 3 × 2 + 2 h − 4 × 3 +  ⁣ ⋯ + ( h − 1 )   ① T(h)=2^{h-2}\times1+2^{h-3}\times2+2^{h-4}\times3+\dotsi+(h-1)\space① T(h)=2h−2×1+2h−3×2+2h−4×3+⋯+(h−1) ①

等式两边同时乘2

2 T ( h ) = 2 h − 1 × 1 + 2 h − 2 × 2 + 2 h − 3 × 3 +  ⁣ ⋯ + 2 ( h − 1 )   ② 2T(h)=2^{h-1}\times1+2^{h-2}\times2+2^{h-3}\times3+\dotsi+2(h-1)\space② 2T(h)=2h−1×1+2h−2×2+2h−3×3+⋯+2(h−1) ②

② − ① ②-① ②−①，错位相减

T ( h ) = 2 h − 1 + 2 h − 2 + 2 h − 3 +  ⁣ ⋯ + 2 − ( h − 1 ) = 2 h − h − 1 T(h)=2^{h-1}+2^{h-2}+2^{h-3}+\dotsi+2-(h-1)=2^h-h-1 T(h)=2h−1+2h−2+2h−3+⋯+2−(h−1)=2h−h−1

h = log ⁡ 2 ( n + 1 ) h=\log_2(n+1) h=log2​(n+1)代入，取最高项，化简得

时间复杂度为 O ( n ) O(n) O(n)

通过计算发现，两种方式的时间复杂度是不一样的。

向下调整的方法因为少调整了一层，明显更快一些。

排序

升序要建什么堆？

如果建小堆，最小的数已经在第一个位置了，剩下的元素之间的关系已经乱了，要重新建堆，麻烦。

如果建大堆，然后把最大的数交换到最后一个位置，再对第一个元素向下调整，明显更好一些。

void HeapSort(int* a, int n)
{
    //向下调整 O(n)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	size_t end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

所以升序建大堆，降序建小堆

时间复杂度： O ( n log ⁡ n ) O(n\log n) O(nlogn)，建堆是 O ( n ) O(n) O(n)，排序是 O ( n log ⁡ n ) O(n\log n) O(nlogn)

空间复杂度： O ( 1 ) O(1) O(1)

Top-K问题

找出N个数中最大或最小的前K个。

N一般比较大，K比较小。

比如：专业前10名，评分最高的前250部电影，世界500强等等。

我们先讨论找最大的前K个。

不难想到这样几种方法：

  1. 直接排序，时间复杂度 O ( N log ⁡ N ) O(N\log N) O(NlogN)；空间复杂度 O ( 1 ) O(1) O(1)
  2. 建立 N N N个数的大堆，pop K K K次，时间复杂度 O ( N + K log ⁡ N ) O(N+K\log N) O(N+KlogN)，当 N ≫ K N\gg K N≫K时，时间复杂度为 O ( N ) O(N) O(N)；空间复杂度 O ( 1 ) O(1) O(1)

有时候 N N N可能非常大，比如从100亿个数中找最大的前10个。

100亿个整型大约是37GB，内存放不下。

这样上面的两种方法就都不行。

如何求解？

  • 用K个数建一个小堆，后面的数和堆顶元素比较
  • 如果比堆顶元素大，则交换，向下调整。

由于堆顶一直是堆中最小的元素，后面有比它还大的，就进堆了。

这样就可以保证堆中的元素就是最大的前 K K K个。

K K K个数在内存中，后面的数从文件中读取即可，也解决了内存放不下的问题。

时间复杂度： O ( K + ( N − K ) log ⁡ K ) O(K+(N-K)\log K) O(K+(N−K)logK)，当 N ≫ K N\gg K N≫K时，时间复杂度为 O ( N ) O(N) O(N)

空间复杂度： O ( K ) O(K) O(K)，别看空间复杂度大了点，但是只要K个数存在内存中，而上面两种方法必须同时把N个数都放进内存。

void PrintTopK(int* a, int n, int k)
{
	int* kminHeap = (int*)malloc(sizeof(int) * k);
	assert(kminHeap);

	for (int i = 0; i < k; ++i)
	{
		kminHeap[i] = a[i];
	}

	// 建小堆
	for (int j = (k - 1 - 1) / 2; j >= 0; --j)
	{
		AdjustDown(kminHeap, k, j);
	}

	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	for (int i = k; i < n; ++i)
	{
		if (a[i] > kminHeap[0])
		{
			kminHeap[0] = a[i];
			AdjustDown(kminHeap, k, 0);
		}
	}

	for (int j = 0; j < k; ++j)
	{
		printf("%d ", kminHeap[j]);
	}
	printf("\n");
	free(kminHeap);
}

找最小的前K个，把小堆改成大堆，后面的元素比堆顶小就进堆。

总结

本节我们学习了堆的实现以及堆的应用，实现了堆排序，解决了TopK问题。

那么，二叉树顺序结构的重要部分——堆，就到此结束了。

下节开始学习二叉树的链式结构。

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/662835.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-18
下一篇 2022-04-18

发表评论

登录后才能评论

评论列表（0条）

保存