本章重点
- 二叉树的顺序结构
- 堆的概念及结构
- 堆的实现
- 堆的调整算法
- 堆的创建
- 堆排序
- TOP-K问题
1.二叉树的顺序结构
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
访问结点的规律：
//访问孩子节点 leftchild = parent*2+1 rightchild = parent*2+2 //访问父亲结点 parent = (child-1)/2
2.堆的概念及结构
堆的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
- 大堆：任何父亲节点 >= 孩子结点
- 小堆：任何父亲节点 <= 孩子结点
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
解析：
堆（Heap）是一种特殊的树形数据结构，它通常有两种类型：小堆（Min Heap）和大堆（Max Heap）。在小堆中，父节点的值小于或等于其子节点的值，而在大堆中，父节点的值大于或等于其子节点的值。
要判断一个序列是否是堆，需要检查该序列是否满足堆的性质。我们发现A符合大堆的性质父节点的值大于或等于其子节点的值。
2.已知小根堆为8,15,10,21,34,16,12，删除关键字 8 之后需重建小堆，在此过程中，关键字之间的比较次数是（）。
A 1
B 2
C 3
D 4
解析：
在一个小根堆中删除根节点后，需要重新构建小根堆。删除根节点后，通常会将堆的最后一个元素移动到根的位置，然后通过与其子节点的比较来逐级下移，以确保小根堆的性质得以恢复。
给定的小根堆是：8, 15, 10, 21, 34, 16, 12。
首先删除根节点8后，将最后一个元素12移到根的位置，得到：12, 15, 10, 21, 34, 16。
然后，我们需要逐级下移12，直到小根堆性质得以恢复。在这个过程中，我们将12与其子节点进行比较，选择较小的子节点来交换位置。
第一次比较：12与15比较，不需要交换。
第二次比较：12与10比较，需要交换。
第三次比较：12与16比较，不需要交换。
因此，关键字之间的比较次数是3次。
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)
堆排序是一种基于堆数据结构的排序算法，通常会建立一个最大堆（Max Heap）或最小堆（Min Heap）来进行排序。在这里，我们需要建立一个最大堆。
初始堆的建立过程通常是从数组的末尾开始，逐步将元素向上移动，以满足堆的性质。对于给定的排序码数组(5 11 7 2 3 17)，初始堆的建立步骤如下：
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]
3.堆的实现
这里的堆是使用数组实现的，博主重点介绍堆的删除和插入接口，其他接口同顺序表相同，这里就不过多赘述了。
typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; // 堆的初始化 void HeapInit(HP* php); // 堆的打印 void HeapPrint(HP* php); // 堆的销毁 void HeapDestroy(HP* php); //堆的创建 void HeapInitArray(HP*php, int* a, int n); // 堆的插入 void HeapPush(HP* php, HPDataType x); // 堆的删除 void HeapPop(HP* php); // 取堆顶的数据 HPDataType HeapTop(HP* php); // 堆的数据个数 int HeapSize(HP* php); // 堆的判空 bool HeapEmpty(HP* php);
3.1堆的插入：void HeapPush(HP* php, HPDataType x)
- 先将元素插入到堆的末尾，即最后一个孩子之后。
- 插入之后如果堆的性质遭到破坏，将信新插入节点顺着其双亲往上调整到合适位置即可，即向上调整。
- 向上调整结束的条件是child等于0，parent等于-1，但是我们写的循环结束条件是child大于0，因为parent的值不会是-1，而是0，这里可以去看我的另外一篇文章，里面介绍了c语言取整规则：链接
void Swap(HPDataType* p1, HPDataType* p2) { HPDataType temp = *p1; *p1 = *p2; *p2 = temp; } //向上调整 void AdjustUP(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] < a[parent]) { Swap(&a[child], &a[parent]);//交换 child = parent; parent = (parent - 1) / 2; } else { break; } } } // 堆的插入 void HeapPush(HP* php, HPDataType x) { assert(php); if(php->size == php->capacity) { int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2; HPDataType* temp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity); if (temp == NULL) { perror("realloc fail"); exit(-1); } php->a = temp; php->capacity = newCapacity; } php->a[php->size] = x; php->size++; AdjustUP(php->a, php->size - 1); }
3.2堆的删除：void HeapPop(HP* php)
- 将堆顶元素与堆中最后一个元素进行交换。
- 删除堆中最后一个元素。
- 将堆顶元素向下调整到满足堆特性为止。
- 向下调整的结束条件是child等于叶子结点。
void Swap(HPDataType* p1, HPDataType* p2) { HPDataType temp = *p1; *p1 = *p2; *p2 = temp; } //向下调整 void AdjustDown(HPDataType* a, int n, int parent) { int child = parent * 2 + 1; //parent到叶子结点就结束 while (child < n) { //可能不存在右孩子 if (child + 1 < n && a[child] > a[child + 1]) { child++; } if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } // 堆的删除 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); }
【完全二叉树魔法：顺序结构实现堆的奇象】（中）：https://developer.aliyun.com/article/1424933
