三、二叉树顺序结构及实现---堆实现
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
1.堆的分类
堆可以分为大根堆和小根堆 ：
大根堆：所有父亲结点都大于等于孩子结点；
小根堆：所有父亲结点都小于等于孩子结点；
2.堆的实现
这里以大堆为例
1.堆数据的初始化 、销毁、打印、交换
//堆的初始化 void HeapInit(HP* hp) { assert(hp); hp->a = NULL; hp->size = hp->capacity = 0; } //堆的销毁 void HeapDestroy(HP* hp) { assert(hp); free(hp->a); hp->capacity = hp->size = 0; } //堆的数据打印 void HeapPrint(HP* hp) { assert(hp); for (int i = 0; i < hp->size; i++) { printf("%d ", hp->a[i]); } printf("\n"); } //堆的数据交换 void Swap(HPDataType* px, HPDataType* py) { HPDataType tmp = *px; *px = *py; *py = tmp; }
2.堆向上调整算法
以大堆为例，应该是大的数据在上，每一层都比下一层数据要大；当数据插入时，如果插入了一个较大的数，我们需要把这个数据向上调整，如果插入的数据比上一层的数据大就调整（即孩子大于父亲），知道调整到根结束；如果是小堆，只需要把符号改变即可；
//向上调整函数（大堆用大于，小堆用小于） void AdjustUp(int* a,int child) { assert(a); 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; } } }
3.堆向下调整算法
以大堆为例，当我们要删除堆顶的数据时：
如何解决：向下调整算法
思路：我们将堆顶的数据和堆最后一个数据进行交换，元素个数减去1，那么就不会访问到我们要删除的数据了，交换上来的堆顶的数据（大堆为例）是一个较小值，把这个较小值进行向下调整，直至满足大根堆；
//向下调整函数（大堆用大于，小堆用小于） void AdjustDown(int* a, int n, int parent) { assert(a); int child = parent * 2 + 1; while (child < n) { //选出左右孩子中大的那个 if (child + 1 < n && a[child + 1] > a[child]) { ++child; } //如果大的孩子大于父亲，则交换，并继续向下调整 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }
4.堆的数据插入
参考向上调整算法
//堆的数据插入 void HeapPush(HP* hp, HPDataType x) { assert(hp); if (hp->size == hp->capacity) { size_t newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2; HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newcapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } hp->a = tmp; hp->capacity = newcapacity; } hp->a[hp->size] = x; hp->size++; AdjustUp(hp->a, hp->size - 1); }
5.堆的数据删除
参考向下调整算法
//堆的数据删除 void HeapPop(HP* hp) { assert(hp); assert(!HeapEmpty(hp)); Swap(&hp->a[0], &hp->a[hp->size - 1]); hp->size--; AdjustDown(hp->a, hp->size, 0); }
6.取堆顶的数据、堆的数据个数、堆的判空
//取堆顶的数据 HPDataType HeapTop(HP* hp) { assert(hp); assert(!HeapEmpty(hp)); return hp->a[0]; } //堆的数据个数 int HeapSize(HP* hp) { assert(hp); return hp->size; } //堆的判空 bool HeapEmpty(HP* hp) { assert(hp); return hp->size == 0;
3.堆的应用
1.Top-k问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能 数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决;
基本思路如下：
1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆;
前k个最小的元素，则建大堆;
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素;
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素;
void PrintTopK(int* a, int n, int k) { // 1. 建堆--用a中前k个元素建堆 // 2. 将剩余n-k个元素依次与堆顶元素交换，不满足则替换 HP hp; HeapInit(&hp); for (int i = 0; i < k; i++) { HeapPush(&hp, a[i]); } //剩下的N-K个数跟堆顶的数据比较，比他大就替换他进堆 for (int i = k; i < n; i++) { if (a[i] > HeapTop(&hp)) { //方法1： HeapPop(&hp); HeapPush(&hp, a[i]); //方法2： //hp.a[0] = a[i]; //AdjustDown(hp.a, hp.size, 0); } } HeapPrint(&hp); HeapDestroy(&hp); } //在N个数中找出最大的前k个 or 在N个数中找出最小的前k个 void TestTopk() { int n = 10000; int* a = (int*)malloc(sizeof(int) * n); srand(time(0)); for (size_t i = 0; i < n; ++i) { a[i] = rand() % 1000000; } //再去设置10个比100w大的数 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; }
2.堆排序 （含动图分析）
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
1. 建堆
升序：建 大 堆
降序：建 小 堆
2. 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
代码1：
利用向上调整构建大堆，然后进行向下调整进行排序；
//排升序建大堆 排降序建小堆 //堆排序 void HeapSort(int* a, int n) { assert(a); //把a数组构建成堆（假设构建成小堆） //方法1 for (int i = 1; i < n; i++) { AdjustUp(a, i); } //移除选数，调堆 //O(N*logN) for (int end = n - 1; end > 0; --end) { Swap(&a[end], &a[0]); //再调堆，选出次小的数 AdjustDown(a, end, 0); } } int main() { int a[] = { 70,56,30,25,15,10,75 }; for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { printf("%d ", a[i]); } printf("\n"); HeapSort(a, sizeof(a) / sizeof(a[0])); for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { printf("%d ", a[i]); } printf("\n"); return 0; }
上面的动图是在利用for循环把数组中的进行了向上 调整，利用循环相当于就是在堆上插入数据，然后通过下标的访问，交换首尾的数据，然后对其交换上来的数据进行向下调整，以此类推；
向下调整的前提：
大堆向下调整，采用向下调整必须左子树和又子树都是大堆；
小堆向下调整，采用向下调整必须左子树和又子树都是小堆；
代码二：
利用向下调整构建大堆，然后再次向下调整进行排序；
考虑一个问题：
如何解决：
最后进行排序和上面的动图一样；
//排升序建大堆 排降序建小堆 //堆排序 void HeapSort(int* a, int n) { assert(a); //方法2 --O(N) for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } //移除选数，调堆---O(N*logN) for (int end = n - 1; end > 0; --end) { Swap(&a[end], &a[0]); //再调堆，选出次小的数 AdjustDown(a, end, 0); } }
