初阶数据结构 堆的问题详解 （三）

题目一

4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）

A 11
B 10
C 8
D 12

我们有最大的节点如下

假设最大高度为10 那么它的最多节点应该是有1023

假设最大高度为9 那么它的最多节点应该是 511

所以说这一题选B

题目二

5.一个具有767个节点的完全二叉树，其叶子节点个数为（）

A 383
B 384
C 385
D 386

还是一样 我们假设0度（叶节点）为X0 1度为X1 二度的为X2

根据前面得到的结论

X2 = X0 - 1

我们有

2X0 -1 + X1= 767

2X0 = 768 - X1

这个时候的X1为0

所以说叶节点的个数为384

该题选B

题目三 TOP K 问题

在N个数中找最大的前K个

解法一

排序 这个很简单了 就不多题 一个快排就搞定了

解法二

将N个数依次插入到大堆中 POPK次 就能取到最大的数

解法三

当我们需要寻找的数特别大的时候 比如说这个数是十个亿

十个亿就是四十亿个字节

大概就是4个G左右的内存

这样子的内存就直接否了解法一和解法二

我们创建一个K个数的小堆

比较堆的首元素的大小和要插入数字的大小

如果说插入的数字大于首元素 那么就替换首元素 之后向下调整

这样子到最后在这个堆里面留下的肯定是最大的K个数

大家仔细想想看是不是

（因为最大的数肯定会沉到最下面）

我们来简单实现一下这个算法的逻辑

我们首先先创建一个小堆

然后插入100个数据

之后开始逐个比较堆顶元素和需要插入的元素的大小

如果说堆顶元素小于我们需要插入的元素

那么删除堆顶元素 之后插入我们的元素

大体思路就是这样子

题目四 堆排序

解法一

建立一个N个数的小堆 POP N次 每次POP之前取出最前面的元素

这种方式显然是可以的 我们写一段代码来验证下试试

HeapType* HeapSort1(Hp* obj,int size)
{
	// assert
	assert(obj);
	assert(obj->arr);
	assert(obj->size != 0);



	// 这里开始排序 创建一个新数组 存放这些元素
	HeapType* a = (HeapType*)malloc(sizeof(HeapType) * obj->size);


	// 存放元素
	int i = 0;
	for (i = 0; i < size; i++)
	{
		a[i] = HeapTop(obj);
		HeapDelete(obj);
	}
	return a;

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

解法二 （空间复杂度为O（1））

这个解法要求我们在原地将数组先调整成堆结构

这里还是以小堆为例

一种解法是从上面开始 将最上面的一个元素当作是小堆

然后后面的数字依次向上调整

代码表示如下

void test1()
{
	// 设置一个数组完成堆排序
	int arr[] = { 1,6,43,7,8,9,2,45,7 };
	int size = sizeof(arr) / sizeof(arr[0]);

	// 我们先将这个数组构造成堆的形式 
	int i;
	for (i = 1; i < size; i++)
	{
		HeapAdjustup(arr, i);
	}

	for ( i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}


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

我们来看看效果

可以实现

我们发现 如果采用小堆的话 我们是无法完成排序的

又或者说我们排序的时间复杂度回事N*N

这是绝对不可以的

这个时候我们采用大堆开始试试

我们可以发现 这是一个完美大堆

这个时候我们只需要将 第一个元素和最后一个元素交换位置

然后让堆的大小减少一

这样子就能在logN的时间复杂度内 完成排序

代码表示如下

void test1()
{
	// 设置一个数组完成堆排序
	int arr[] = { 1,6,43,7,8,9,2,45,7 };
	int size = sizeof(arr) / sizeof(arr[0]);

	// 我们先将这个数组构造成堆的形式 
	int i;
	for (i = 1; i < size; i++)
	{
		HeapAdjustup(arr, i);
	}

	for ( i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}


	for ( i = size-1; i > 0; i--)
	{
		int tmp = 0;
		// 交换位置
		tmp = arr[i];
		arr[i] = arr[0];
		arr[0] = tmp;

		HeapAdjustDown(arr, i);
	}


	printf("\n");


	for (i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}

}
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

这样就完成了时间复杂度为logN 空间复杂度为1的堆排序啦