本文主要是介绍【数据结构】二叉树的顺序结构，详细介绍堆以及堆的实现，堆排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
1. 二叉树的顺序结构
2. 堆的概念及结构
3. 堆的实现
3.1 堆的结构
3.2 堆的初始化
3.3 堆的插入
3.4 堆的删除
3.5 获取堆顶数据
3.6 堆的判空
3.7 堆的数据个数
3.8 堆的销毁
4. 堆的应用
4.1 堆排序
4.1.1 向下调整建堆的时间复杂度
4.1.2 向上调整建堆的时间复杂度
4.2 TOP-K问题
5. 选择题
1. 二叉树的顺序结构
1. 普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。
2. 完全二叉树更适合使用顺序结构存储。
3. 通常把堆(一种二叉树)使用顺序结构的数组来存储。
2. 堆的概念及结构
1. 将根节点最大的堆叫做大堆或大根堆，根节点最小的堆叫做小堆或小根堆。
2. 大堆：树的任何一个父亲都大于等于他的孩子。
3. 小堆：树的任何一个父亲都小于等于他的孩子。
4. 堆总是一棵完全二叉树。
3. 堆的实现
3.1 堆的结构
1. 堆本质是一个数组。
typedef int HeapDataType; typedef struct Heap {HeapDataType* arr; //指向数组size_t size; //数据个数size_t capacity; //容量 }Heap;
3.2 堆的初始化
1. 传入的堆指针不能为空。
2. 将数组指针置空，容量和个数置0。
void HeapInit(Heap* ph) {//1. 传入的堆指针不能为空。assert(ph);//2. 将数组指针置空，容量和个数置0。ph->arr = NULL;ph->size = ph->capacity = 0; }
3.3 堆的插入
1. 插入一个数就是在数组尾插，插入前是堆，插入后不一定是堆，需要检测。
2. 插入一个数只会对它所在的路径有影响，需要用向上调整算法。
3. 假设原本是小堆，那么新插入的数和他的父亲比较，比他父亲小就交换，然后继续往上比较，直到变成根位置。
4. 最好的情况是不用调整，最坏的情况是调整到根位置。
代码实现：
1. 传入的堆指针不能为空。
2. 插入前判断需不需要扩容。
3. 最后一个位置插入，然后size++。
4. 插入后使用向上调整算法。
向上调整算法：
1. 下标关系：parent = (child-1) / 2。
2. 假设是小堆，当孩子小于父亲，孩子和父亲的值交换，孩子再走到父亲的位置继续向上比较，如果孩子大于等于父亲就直接break不用比较了，或者孩子到根位置结束。
void Swap(HeapDataType* h1, HeapDataType* h2) {HeapDataType tmp = *h1;*h1 = *h2;*h2 = tmp; }void AdjustUp(HeapDataType* arr, int child) {int parent = (child - 1) / 2;//孩子到根位置结束while (child){//1. 小堆：当孩子小于父亲，孩子和父亲的值交换。if (arr[child] < arr[parent]) Swap(&arr[child], &arr[parent]);//2. 如果孩子大于等于父亲就直接break不用比较了else break;//3. 孩子再走到父亲的位置继续向上比较child = parent;parent = (child - 1) / 2;} }void HeapPush(Heap* ph, HeapDataType data) {//1. 传入的堆指针不能为空。assert(ph);//2. 插入前判断需不需要扩容。size_t capacity = ph->capacity == 0 ? 4 : ph->capacity * 2;HeapDataType* tmp = realloc(ph->arr, sizeof(HeapDataType) * capacity);if (tmp == NULL){perror("realloc");return;}ph->arr = tmp;ph->capacity = capacity;//3. 最后一个位置插入，然后size++。ph->arr[ph->size++] = data;//4. 插入后使用向上调整算法。AdjustUp(ph->arr, ph->size - 1); }
插入的时间复杂度：
1. 插入的最坏情况就是从叶子一直走到根，也就是树的高度，假设节点数为N，完全二叉树的节点范围是2^(h-1)到2^h - 1，2^(h-1) = N 或 2^h - 1 = N, 可得h = logN(2为底) + 1 或 h = log(N+1)(2为底)，所以O(N) = logN(2为底)。
2. 插入的时间复杂度主要看向上调整算法，同理删除主要看向下调整算法，它们的时间复杂度都是logN,以2为底。
3.4 堆的删除
1. 传入的堆指针不能为空。
2. 堆不能为空。
3. 删除是删堆顶的数据，先将堆顶数据和最后一个数据交换，然后删除最后一个数据。
4. 从堆顶数据开始向下调整，使用向下调整算法的前提：左子树和右子树是堆。
向下调整算法：
1. 假设是小堆，child = parent*2 + 1，先假设左孩子是小的，再将左孩子和右孩子比一下，谁小谁就是child。记得判断一下右孩子是否存在。
2. parent 和 child 比较，parent比child大就交换，然后parent走到child的位置继续往下比较，直到比child小或没有child。
void AdjustDown(HeapDataType* arr, int size, int parent) {//小堆：先假设左孩子是小的，再将左孩子和右孩子比一下，谁小谁就是child。记得判断一下右孩子是否存在。int child = parent * 2 + 1;while (child < size){//1. 小堆：parent和较小的孩子比较if (child + 1 < size && arr[child + 1] < arr[child]) child++;//2. parent 和 child 比较，parent比child大就交换if (arr[parent] > arr[child]) Swap(&arr[parent], &arr[child]);else break;//3. 然后parent走到child的位置继续往下比较parent = child;child = parent * 2 + 1;} }void HeapPop(Heap* ph) {//1. 传入的堆指针不能为空。assert(ph);//2. 堆不能为空。assert(!HeapEmpty(ph));//3. 删除是删堆顶的数据，先将堆顶数据和最后一个数据交换，然后删除最后一个数据。Swap(&ph->arr[0], &ph->arr[ph->size - 1]);ph->size--;//4. 从堆顶数据开始向下调整。AdjustDown(ph->arr, ph->size, 0); }
3.5 获取堆顶数据
1. 传入的堆指针不能为空。
2. 堆不能为空。
3. 返回数组第一个元素。
HeapDataType HeapTop(Heap* ph) {//1. 传入的堆指针不能为空。assert(ph);//2. 堆不能为空。assert(!HeapEmpty(ph));//3. 返回数组第一个元素。return ph->arr[0]; }
3.6 堆的判空
1. 传入的堆指针不能为空。
2. 判断size是否为0，空返回真。
bool HeapEmpty(Heap* ph) {//1. 传入的堆指针不能为空。assert(ph);//2. 判断size是否为0，空返回真。return ph->size == 0; }
3.7 堆的数据个数
1. 传入的堆指针不能为空。
2. 返回size。
int HeapSize(Heap* ph) {//1. 传入的堆指针不能为空。assert(ph);//2. 返回size。return ph->size; }
3.8 堆的销毁
void HeapDestroy(Heap* ph) {assert(ph);free(ph->arr);ph->size = ph->capacity = 0; }
完整代码：Heap/Heap · 林宇恒/DataStructure - 码云 - 开源中国 (gitee.com)
4. 堆的应用
4.1 堆排序
堆排序利用堆的思想来进行排序，总共分为两个步骤：
第一步：建堆。
用向上调整算法建堆
1. 从第二个元素开始，将每个元素看作堆的插入向上调整。
2. 升序建大堆，降序建小堆。
用向下调整算法建堆
1. 叶子节点是不需要向下调整的，所以是从最后一个父亲节点开始向下调整。
2. 然后继续找前面的父亲节点向下调整直到第一个节点调整完。
第二步：利用堆删除的思想来进行排序。
1. 将首尾数据交换。
2. 交换到后面的数据是我们想要的不动，交换到堆顶的数据开始做向下调整。
2. 每交换一次，需要调整的个数就减一，直到剩下一个时就不用调整了。
void HeapSort(int* arr, int len) {//第一步：建堆。//从第二个元素开始，将每个元素看作堆的插入向上调整。//升序建大堆，降序建小堆。for (int i = 1; i < len; i++) AdjustUp(arr, i);//向下调整建堆//parent = (child-1) / 2, 这里最后一个child是len-1for (int i = (len - 1 - 1) / 2; i >= 0; i--) AdjustDown(arr, len, i);//第二步：利用堆删除的思想来进行排序。int end = len - 1;while (end>0){//首尾数据交换Swap(&arr[0], &arr[end]);//首数据向下调整，这里传入end指的是调整end前面的数据。AdjustDown(arr, end, 0);//调整完后最后一个位置交换后不用调整。end--;} }
排升序不建小堆的原因：当我们建完小堆，也就是找出了最小的一个，那我们要从剩下的数据找第二小的，这样又需要重新建小堆。
4.1.1 向下调整建堆的时间复杂度
从最后一个父亲节点开始则所有节点移动的总步数为：
F(n) = 2^0*(h-1) + 2^1*(h-2) + ... + 2^(h-2)*1 + 2^(h-1)*0
错位相减可得：F(n) = -2^0*h + 2^0*1 + 2^1*1 + ... + 2^(h-2)*1 + 2^(h-1)*1
再次错位相减可得：F(n) = 2^h - 1 - h
又因节点个数n和高度h的关系是(视为满二叉树)：n = 2^h -1，h = log(n+1)(2为底)
所以F(n) = n - log(n+1)(2为底)
时间复杂度也就是所有节点移动的总步数：O(n) = n
4.1.2 向上调整建堆的时间复杂度
从第二个节点开始，则所有节点移动的总步数为：
F(n) = 2^1*1 + 2^2*2 + 2^3*3 + ... + 2^(h-1)*(h-1)
错位相减得：F(n) = -2^1 - 2^2 - 2^3 - ... - 2^(h-1) - 2^h + 2^h*h
再次错位相减得：F(n) = 2^h*(h-2) + 2
又因节点个数n和高度h的关系是(视为满二叉树)：n = 2^h -1
所以F(n) = (n+1)(log(n+1)(2为底) - 2) + 2
时间复杂度也就是所有节点移动的总步数：O(n) = n*logn(2为底)
4.2 TOP-K问题
TOP-K问题：求前K个最大或最小的元素，比如：专业前10名、游戏中前100的活跃玩家等。
1. 将前K个数据建堆，求前K个最大的数据就建小堆，反之亦然。
2. 从第K个数据开始往后，每个数据都和堆顶比较。
3. 假设求前K个最大的数据，那么当后面的数据比堆顶数据大时就覆盖堆顶数据然后向下调整，反之亦然。
//造数据 void CreateData() {//打开文件FILE* mtof = fopen("data.txt", "w");if (mtof == NULL){perror("fopen");return;}//随机生成数据写入文件srand((unsigned int)time(NULL));for (int i = 0; i < 10; i++) fprintf(mtof, "%d\n", rand() % 100);//关闭文件fclose(mtof); }//求前K个最大 void TopK(int k) {//打开文件FILE* ftom = fopen("data.txt", "r");if (ftom == NULL){perror("fopen");return;}//将文件数据读进内存int* HeapArr = (int*)malloc(sizeof(int) * k);if (HeapArr == NULL){perror("malloc");return;}for (int i=0; i<k; i++) fscanf(ftom, "%d", &HeapArr[i]);//1. 将前K个数据建堆。for (int i=((k-1)-1)/2; i>=0; i--) AdjustDown(HeapArr, k, i);//2. 从第K个数据开始，每个数据都和堆顶比较int val;while (!feof(ftom)){fscanf(ftom, "%d", &val);//如果比堆顶大就覆盖堆顶，然后向下调整if (val > HeapArr[0]){HeapArr[0] = val;AdjustDown(HeapArr, k, 0);}}//关闭文件fclose(ftom); }
5. 选择题
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]
答：C
这篇关于【数据结构】二叉树的顺序结构，详细介绍堆以及堆的实现，堆排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
