题目一
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; }
解法二 （空间复杂度为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]); } }
我们来看看效果
可以实现
我们发现 如果采用小堆的话 我们是无法完成排序的
又或者说我们排序的时间复杂度回事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]); } }
这样就完成了时间复杂度为logN 空间复杂度为1的堆排序啦
