- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

二叉树和堆(二)

跳动的bit 发表于 2022/05/22 22:14:17 2022/05/22

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

一、二叉树顺序结构及实现

💦 二叉树的顺序结构

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

❓ 操作系统和数据结构这两门学科中都有栈和堆的概念，如何区分 ❔

💦 堆的概念及结构

如果有一个关键码的集合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…，则称为小堆 (或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

❗ 堆的性质 ❕

▶ 堆中某个节点的值总是不大于或不小于其父节点的值；

▶ 堆总是一棵完全二叉树；

---------------------------------------Cut-----------------------------------------

❗ 大(根)堆和小(根)堆 ❕

▶ 大(根)堆，树中所有父亲都大于或者等于孩子，且大堆的根是最大值；

▶ 小(根)堆，树中所有父亲都小于或者等于孩子，且小堆的根是最小值；

💦 堆的概念选择题

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

📝 分析：根据堆的概念分析，A 选项为大根堆；

2、注，请理解下面堆应用的知识再做。已知小根堆为 8, 15, 10, 21, 34, 16, 12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（）

A. 1

B. 2

C. 3

D. 4

📝 分析：

此题考查的是建堆的过程

所以选择 C 选项

3、注，请理解下面堆应用的知识再做。一组记录排序码为 (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)

📝 分析：

此题考查的是堆排序建堆的过程

根据下面堆排序的过程分析，选择 C 选项

4、、注，请理解下面堆应用的知识再做。最小堆 [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]

📝 分析：

此题考查的是 Pop 堆顶后，重新建堆的变化

所以选择 C 选项

💦 堆的实现

1、堆向下调整算法

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

❗ 建堆 ❕
有一个随机值的数组，把它理解成完全二叉树，并模拟成堆 (大堆/小堆)

-------------------------------------------------------Cut---------------------------------------------------------

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

❓ 观察上面这组数据 ❔
根下面的左右子树都是小根堆，其实堆向下调整算法就是针对这种特殊数据结构

-------------------------------------------------------Cut---------------------------------------------------------

❓ 针对于这种类型的数据应该怎么调堆 ❔
思路：从根开始与左右孩子比较，如果孩子比父亲小，则两两交换位置，再继续往下调，直到左右孩子都比父亲大或者调到叶子
具体见下图：

-------------------------------------------------------Cut---------------------------------------------------------

❓ 如果不满足左右子树是堆，怎么调整 ❔

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

根的左右子树 37、28 都不满足：这里的想法就是先让左右子树先满足；而对于左右子树 37、28 来说又需要让 37 先满足；这样依此类推直至满足堆的条件。那干脆就从倒数的第一棵树，也就是倒数的第一个非叶子节点开始调整

2、堆的创建

❗ 这里从倒数的第一个非叶子节点开始调整 ❕

#include<stdio.h>

//实现父子交换的函数
void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
//实现调整
void AdjustDown(int* arr, int sz, int parent)
{
	//确定左孩子的下标
	int child = parent * 2 + 1;
	//孩子的下标超出数组的范围就停止
	while (child < sz)
	{
		//确定左右孩子中较小/大的那个
			//左孩子大于右孩子，所以让child记录较小孩子的下标 || (arr[child]<arr[child+1]记录较大孩子的下标)
		if (arr[child] > arr[child + 1] && child + 1 < sz)
		{
			child++; //(当只有一个左孩子时，会越界，且后面使用时会发生非法访问)
		}
		//判断父亲和小孩子
			//小孩子小于父亲，则交换，且继续调整 || (arr[child]>arr[parent]大孩子大于父亲，则交换，且继续调整)
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			//迭代
			parent = child;
			//重新确定左孩子的下标(当最后的叶子节点是parent时，这时去确定child会以读的方式越界，但可以不关心)
			child = parent * 2 + 1;
		}
		//小孩子大于父亲，则停止调整
		else
		{
			break;
		}
	}
}
//堆排序 -> 效率更高
void HeapSort(int* arr, int sz)
{
	//建堆
	int i = 0;
	//从最后一棵树开始调整，也就是最后一个节点的父亲
	for (i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, sz, i);
	}
}
int main()
{
	//左右子树都为堆
	int arr1[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	//左右子树都为非堆
	int arr2[] = { 27, 37, 28, 18, 19, 34, 65, 25, 49, 15 };

	HeapSort(arr1, sizeof(arr1) / sizeof(arr1[0]));
	int i = 0;
	for (i = 0; i < sizeof(arr1) / sizeof(arr1[0]); i++)
	{
		printf("%d ", arr1[i]);
	}

	printf("\n");

	HeapSort(arr2, sizeof(arr2) / sizeof(arr2[0]));
	for (i = 0; i < sizeof(arr2) / sizeof(arr2[0]); i++)
	{
		printf("%d ", arr2[i]);
	}
	return 0;
}

💨 输出结果：

小堆

大堆

3、堆的时间复杂度

❓ 证明建堆的时间复杂度是O(N) ❔

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

建堆的调用次数用 T(N) 表示：(从最后一个非叶子节点 <也就是倒数第二层> 开始，最坏的情况下：倒数第二层每个节点最多能向下调 1 次；倒数第三层每个节点最多能向下调 2 次；倒数第四层每个节点最多能向下调 3 次；)

每层节点个数 $\times$ 最坏情况向下调整次数：

T(N) = 2^h-2^ $\times$ 1 + 2^h-3^ $\times$ 2 + … … + 2^0^ $\times$ (h-1)

这里我们从上至下开始

T(N) = 2^0^ $\times$ (h - 1) + 2^1^ $\times$ (h - 2) + 2^2^ $\times$ (h - 3) + 2^3^ $\times$ (h - 4) + … … + 2^h-3^ $\times$ 2 + 2^h-2^ $\times$ 1

❗ 错位相减法 ❕

等号左右两边乘个 2 得到一个新公式，再用新公式减去旧的公式，具体见下图

4、堆的插入

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

5、堆的删除

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

6、堆的代码实现

⚠ 注意 ⚠

▶ 堆的初始化一般是使用数组进行初始化的

▶ 堆的插入数据不分头插、尾插，将数据插入后，原来堆的属性不变

先放在数组的最后一个位置，再向上调整

▶ 堆的删除数据删除的是堆顶的数据，将数据删除后，原来堆的属性不变

为了效率，将第一个和最后一个元素交换，再减容，然后再调整

❗ 这里需要三个文件 ❕

1️⃣ Heap.h，用于函数的声明

#pragma once

//头
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

typedef int HPDataType;

//C++ -> priority_queue 在C++里用的是优先级队列，其底层就是一个堆
//大堆
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
//函数的声明
//交换
void Swap(int* px, int* py);
//向下调整
void AdjustDown(int* arr, int n, int parent);
//向上调整
void AdjustUp(int* a, int child);
//使用数组进行初始化
void HeapInit(HP* php, HPDataType* a, int n);
//回收空间
void HeapDestroy(HP* php);
//插入x，保持它继续是堆
void HeapPush(HP* php, HPDataType x); 
//删除堆顶的数据，保持它继续是堆
void HeapPop(HP* php);
//获取堆顶的数据，也就是最值
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);
//堆的数据个数
int HeapSize(HP* php);
//输出
void HeapPrint(HP* php);

2️⃣ Heap.c，用于函数的定义

#include"Heap.h"


void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void AdjustDown(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (arr[child] < arr[child + 1] && child + 1 < n)
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void AdjustUp(int* 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 HeapPrint(HP* php)
{
	assert(php);

	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
//1、对于HeapCreate函数，结构体不是外面传进来的，而是在函数内部自己malloc空间，再创建的
/* 
HP* HeapCreate(HPDataType* a, int n)
{}
*/
//2、对于HeapInit函数，在外面定义一个结构体，把结构体的地址传进来
void HeapInit(HP* php, HPDataType* a, int n)
{
	assert(php); 
	//malloc空间(当前数组大小一样的空间)
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//使用数组初始化
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = n;
	php->capacity = n;
	//建堆 
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, n, i);
	}
}
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	//空间不够，增容
	if (php->size == php->capacity)
	{
		HPDataType* temp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
		if (temp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			php->a = temp;	
		}
		php->capacity *= 2;
	}
	//将x放在最后
	php->a[php->size] = x;
	php->size++;
	//向上调整
	AdjustUp(php->a, php->size - 1);
}
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);
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	//没有数据获取就报错
	assert(!HeapEmpty(php));
	
	return php->a[0];
}
int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

3️⃣ Test.c，用于测试函数

#include"Heap.h"

void TestHeap()
{
	int arr[] = { 27, 37, 28, 18, 19, 34, 65, 25, 49, 15 };
	HP hp;
	HeapInit(&hp, arr, sizeof(arr)/sizeof(arr[0]));
	HeapPrint(&hp);
	HeapPush(&hp, 18);
	HeapPrint(&hp);
	HeapPush(&hp, 98);
	HeapPrint(&hp);
	printf("\n\n");
	//将堆这数据结构实现好后，我们就可以利用这些接口实现排序
	while(!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));	
		HeapPop(&hp);
	}
	printf("\n");
	
}
int main()
{
	TestHeap();
	return 0;
}

💦 堆的应用

1、堆排序

❓ 堆创建后，如何进行排序 (升序、降序) ❔
升序建大堆；降序建小堆。不是说升序建小堆；降序建大堆不行，而是因为不好：
如果排升序建小堆：
1、选出最小的数，最小的数就放在第一个位置
2、接着就要选次小的数，再选次小的数 … … 。不断的选下去，如何选？
  只能对剩下的 sz-1、sz-2、sz-3 … 个数继续建堆。可想这样的代价是很高的 —— 建堆的时间
  复杂度是 O(N)，整个时间复杂度就是 O(N^2^)，堆的价值没有体现，还不如直接循环遍历
如果排升序建大堆：
1、选出最大的数，与最后一个数交换位置
2、怎么选出次大、次次大？
  堆的结构没有被破坏，且最后一个数不看做堆，左右子树依旧是大堆，向下调整即可
  最多调整 log~2~N 次，整体的时间复杂度是 O(N*log~2~N）
对比效率：

	1000	1000000
O(N^2^)	1000000	1000000000000
O(N*log~2~N)	10000	20000000

❗ 动图画解思路 ❕

升序建大堆

降序建小堆

#include<stdio.h>

void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void AdjustDown(int* arr, int sz, int parent)
{
	int child = parent * 2 + 1;
	while (child < sz)
	{
		if (arr[child] > arr[child + 1] && child + 1 < sz)
		{
			child++; 
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* arr, int sz)
{
	int i = 0;
	for (i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, sz, i);
	}
	//排升序 > 建大堆
	//排降序 > 建小堆
	int end = sz - 1;
	//每次循环都将最小或最大的值与最后一个值交换，且最后一个值不看作堆的内容
	while (end > 0)
	{
		//与最后一个值交换
		Swap(&arr[0], &arr[end]);
		//调整
		AdjustDown(arr, end, 0);
		end--;
	}

}
int main()
{
	//左右子树都为堆
	int arr1[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	//左右子树都为非堆
	int arr2[] = { 27, 37, 28, 18, 19, 34, 65, 25, 49, 15 };

	HeapSort(arr1, sizeof(arr1) / sizeof(arr1[0]));
	int i = 0;
	for (i = 0; i < sizeof(arr1) / sizeof(arr1[0]); i++)
	{
		printf("%d ", arr1[i]);
	}

	printf("\n");

	HeapSort(arr2, sizeof(arr2) / sizeof(arr2[0]));
	for (i = 0; i < sizeof(arr2) / sizeof(arr2[0]); i++)
	{
		printf("%d ", arr2[i]);
	}
	return 0;
}

💨 输出结果：

升序

降序

3、TOP - K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：CSDN总榜前10、世界500强、富豪榜等。

❓ 如何求 ❔

🔑 方法 1：

排序，时间复杂度 O(N*logN)

🔑 方法 2：

建一个 N 个数的堆(优先级队列)，不断选数，选出前 K 个，时间复杂度 O(N+K*log(N))

❗ 假设 N 是十亿，显然前两个方法都不适用 ❕

🔑 方法 3：

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

1️⃣ 用数据集合中前 K 个元素来建堆

▶ 前k个最大的元素，则建小堆

▶ 前k个最小的元素，则建大堆

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

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

❗ 模拟 ❕

创建随机数种子，生成随机数

❓ 怎么知道前十个数就是 TOP - 10 ❔

默认随机生成的数都是小于 1000000 的，然后给随机位置的 10 个数都是比 1000000 要大的，把这 10 个数选出来就说明算法是对的

❗ 这里需要三个文件 ❕

1️⃣ TOP-K.h，用于函数的声明

#pragma once

//头
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<time.h>

typedef int HPDataType;

//C++ -> priority_queue 在C++里用的是优先级队列，其底层就是一个堆
//大堆
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
//函数的声明
//交换
void Swap(int* px, int* py);
//向下调整
void AdjustDown(int* arr, int n, int parent);
//向上调整
void AdjustUp(int* a, int child);
//使用数组进行初始化
void HeapInit(HP* php, HPDataType* a, int n);
//回收空间
void HeapDestroy(HP* php);
//插入x，保持它继续是堆
void HeapPush(HP* php, HPDataType x);
//删除堆顶的数据，保持它继续是堆
void HeapPop(HP* php);
//获取堆顶的数据，也就是最值
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);
//堆的数据个数
int HeapSize(HP* php);
//输出
void HeapPrint(HP* php);

2️⃣ TOP-K.c，用于函数的定义

#include"TOP-K.h"

void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void AdjustDown(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (arr[child] > arr[child + 1] && child + 1 < n)
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void AdjustUp(int* 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 HeapPrint(HP* php)
{
	assert(php);

	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
//1、对于HeapCreate函数，结构体不是外面传进来的，而是在函数内部自己malloc空间，再创建的
/*
HP* HeapCreate(HPDataType* a, int n)
{}
*/
//2、对于HeapInit函数，在外面定义一个结构体，把结构体的地址传进来
void HeapInit(HP* php, HPDataType* a, int n)
{00j000	
	assert(php);
	//malloc空间(当前数组大小一样的空间)
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//使用数组初始化
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = n;
	php->capacity = n;
	//建堆 
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, n, i);
	}
}
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	//空间不够，增容
	if (php->size == php->capacity)
	{
		HPDataType* temp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
		if (temp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			php->a = temp;
		}
		php->capacity *= 2;
	}
	//将x放在最后
	php->a[php->size] = x;
	php->size++;
	//向上调整
	AdjustUp(php->a, php->size - 1);
}
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);
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	//没有数据获取就报错
	assert(!HeapEmpty(php));

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

	return php->size;
}

3️⃣ Test.c，用于函数的测试

#include"TOP-K.h"

void PrintTopK(int* a, int n, int k)
{
	HP hp;
	HeapInit(&hp, a, k);

	int i = 0;
	for (i = k; i < n; i++)
	{
		//比较堆顶的数据
		if (a[i] > HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
	}

	HeapPrint(&hp);
	HeapDestroy(&hp);
}
void TestTopk()
{
	int n = 100000;
	int* a = (int*)malloc(sizeof(int)*n);
	//创建随机数种子
	srand((unsigned int)time(0));
	//生成随机数
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	//如果找出这10个数，说明TOP-K算法是正确的
	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);
}

int main()
{
	TestTopk();
	return 0;
}

点赞
收藏
关注作者

0/1000

抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认取消

加入云驻计划，成为创作者

华为云周边好礼
免费体验产品
特殊身份标识
线下官方门票
内部专家零距离
与10000+优质创作者共同成长

立即加入

二叉树和堆(二)

一、二叉树顺序结构及实现

💦 二叉树的顺序结构

💦 堆的概念及结构

💦 堆的概念选择题

💦 堆的实现

1、堆向下调整算法

2、堆的创建

3、堆的时间复杂度

4、堆的插入

5、堆的删除

6、堆的代码实现

💦 堆的应用

1、堆排序

3、TOP - K问题

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

二叉树和堆(二)

一、二叉树顺序结构及实现

💦 二叉树的顺序结构

💦 堆的概念及结构

💦 堆的概念选择题

💦 堆的实现

1、堆向下调整算法

2、堆的创建

3、堆的时间复杂度

4、堆的插入

5、堆的删除

6、堆的代码实现

💦 堆的应用

1、堆排序

3、TOP - K问题

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

推荐阅读

相关产品