二叉树-堆（补充）

🌟🌟hello，各位读者大大们你们好呀🌟🌟
🚀🚀系列专栏：【数据结构的学习】
📝📝本篇内容：二叉树的基本特性；堆；堆的基本概念；堆的实现；堆的初始化；堆的销毁；堆的插入；取出堆顶的数据；堆的删除；堆的判空；堆的数据个数；交换；打印堆数据；堆的创建；堆排序；完整代码；Top-K问题
⬆⬆⬆⬆上一篇：二叉树（三）
💖💖作者简介：轩情吖，请多多指教(> •̀֊•́ ) ̖́-

1.二叉树的基本特性

上图展示的就是二叉树，我将它的规律也写在上面了
一般我们把二叉树的高度设置从1开始，从0开始的话，空树就是-1，就不太合适了
一棵N个结点的树有N-1条边
假设二叉树的第k层是满的，它的结点数为2^(k-1)个
我们的二叉树还分为满二叉树和完全二叉树，下图展示了二者的对比图

满二叉树：一个二叉树，如果每一层的结点都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数是2^k-1,则就是满二叉树。
完全二叉树：前N-1层是满的，最后一层可以不满，但是必须从左往右是连续的，满二叉树是一种特殊的完全二叉树。
我们先来分析一下满二叉树的特性：
假设满二叉树有k层，则它的最后一层的结点有2^(k-1)个
假设满二叉树有k层，一棵满二叉树一共有2^k-1个结点，计算方法如下：

其实还有一个小技巧：我们的二进制的每一位的值和二叉树的每一层的结点数相等的，假设我们的二进制为11111111，它是一个unsigned char类型的最大值，此时我们计算它的十进制就通过它的再高一位的值-1计算得出，即2^8-1=255。类比到二叉树，即下一层的结点数-1，设最后一层的结点个数为2 ^3，第4层，计算整棵二叉树的结点数为2 ^4-1。

设满二叉树的总结点数为N个，树的高度为log₂(N+1)，通过2^k-1=N计算可得
完全二叉树的特性：
设完全二叉树有k层，完全二叉树总共结点最少就是最后一层只有一个，即2^(k-1)个；最多也就是满二叉树，即2 ^k-1个结点

最多不用讲怎么计算了，最少可以用之前讲的错位相减法来计算，也可以二叉树的规律来算：假设完全二叉树一共k层；那么根据前面讲的，除去最后一层一个结点，它就是一棵满二叉树，共k-1层，根据满二叉树的总共结点公式，总结点数为2^ (k-1)-1个；那么再加上去掉的一个结点，完全二叉树的总结点数即为2^(k-1)个，如下图

对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2,则有n2=n0+1

2.堆

2.1.堆的基本概念

接下来讲的堆是二叉树的一种存储方式，从逻辑结构（想象的结构）上看我们的堆是一棵完全二叉树，从存储结构上看堆是数组
我们的堆还分为大根堆（大堆）和小根堆（小堆）
大堆：父结点大于等于孩子结点，并且子树也同样的，大堆的根结点在整个堆中是最大的元素
大堆：父结点小于等于孩子结点，并且子树也同样的，小堆的根结点在整个堆中是最小的元素


之所以我们我们的数组只能表示完全二叉树，是因为不是完全二叉树会有空间浪费，如下图

并且我们的堆是数组存储还有一个特性：
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

2.2.堆的实现

2.2.1.基本结构

//Heap.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>
typedef int T;//堆数据类型typedef struct Heap
{T* arr;//堆的存储位置int size;//堆的数据个数int capacity;//堆的容量
}Heap;void HeapInit(Heap* heap);//堆的初始化
void HeapCreate1(Heap* heap, T* a, int n);//创建堆方法1
void HeapCreate2(Heap* heap, T* a, int n);//创建堆方法2
void HeapDestory(Heap* heap);//将堆销毁
void HeapPush(Heap* heap,T x);//堆的构建
void HeapPrint(Heap* heap);//将堆数据打印出来
T HeapTop(Heap* heap);//取出堆顶数据
void HeapPop(Heap* heap);//删除堆顶数据
int HeapSize(Heap* heap);//堆的数据个数
bool HeapEmpty(Heap* heap);//堆是否为空void swap(T* x, T* y);//交换
void AdjustUp(T* arr, int child);//向上调整
void AdjustDown(T* arr, int size, int parent);//向下调整void HeapSort(int* arr,int n);//堆排序

上述代码已经将存储堆的结构体已经写好，同时把我们的堆的各种函数调用已经声明好了

2.2.2.堆的初始化

void HeapInit(Heap* heap)//堆的初始化
{assert(heap);heap->arr = NULL;heap->capacity = heap->size = 0;
}

我们这边的写法是一开始不给数组任何的空间，后期直接使用realloc开辟

2.2.3.堆的销毁

void HeapDestory(Heap* heap)//将堆销毁
{assert(heap);free(heap->arr);//释放空间heap->size = heap->capacity = 0;
}

不要忘记释放开辟的空间！！！

2.2.4.堆的插入

由于我们数组的特性，头插需要移动元素什么的，效率极低，但是可以尾插，所以说堆一般性就都是在尾部插入

//我们默认建立大堆哈
void AdjustUp(T* arr,int child)//向上调整
{int parent = (child - 1) / 2;//找父结点//使用parent>=0有点不合理，倒数第二次运行循环时child已经是0了，应该结束//但是（child-1）/2导致parent依旧为0，再次进入循环，然后通过else中的breakwhile (child>0){//孩子结点大于父结点if (arr[child] > arr[parent]){//交换swap(&arr[child], &arr[parent]);//继续向上调整child = parent;parent = (child - 1) / 2;}else{//如果孩子结点小于父结点，就不用向上调整了break;}}
}void HeapPush(Heap* heap, T x)//堆的插入
{assert(heap);//空间不足开辟内存if (heap->size == heap->capacity){int newcapacity = heap->capacity == 0 ? 4 : heap->capacity * 2;//realloc的第一个元素是NULL的话，功能和malloc一样T* newarr = (T*)realloc(heap->arr, newcapacity*sizeof(T));if (newarr == NULL){perror("realloc fail");exit(-1);}//修改已经开辟好空间后的信息heap->arr = newarr;//realloc可能不在原位扩容，所以说这一步是必要的heap->capacity = newcapacity;}//正式插入heap->arr[heap->size] = x;heap->size++;//数据个数+1//向上调整，保证是一个堆AdjustUp(heap->arr, heap->size - 1);
}

我们默认建立的是大堆哈，如果想要建立小堆，只需要将向上调整中的比较孩子结点和父结点的>变成<即可

代码和图片也展示在了上面，可以通过图片来理解一下，之所以这样写是因为我们在没有进行插入前，我们的结构肯定是堆的，但是插入后，我们需要进行调整才能保证堆的结构，我们写的是大堆，
因此需要和父结点进行比较，如果比父结点大，那么继续交换。但是由于交换后，可能还是比祖父结点大，也就还需要不停地调整。向上调整是对插入结点的祖先进行调整

2.2.5.取出堆顶的数据

T HeapTop(Heap* heap)//取出堆顶数据
{	assert(heap);assert(heap->size > 0);return heap->arr[0];
}

我们的可以用于Top-k问题，举个例子，我们在10000个人里面，选出最有钱的人，我们的堆就发挥了大用处，因为它的堆顶的数据，即数组第一个元素是最大（最小）的，我们只需要取出后，再删除就可以选出第二大的…第n大的，因此我们还需要来实现一下删除才能彻底理解

2.2.6.堆的删除

void AdjustDown(T* arr, int size,int parent)
{//选出左孩子和右孩子中较大的那个//假设较大的是左孩子int child = parent * 2 + 1;//孩子结点存在才向下调整while (child<size){if (child + 1 < size && arr[child + 1] > arr[child]){//进行判断，如果右孩子大于左孩子，就+1，因为左孩子和右孩子之间就相差1child++;}//孩子结点大于父节点，就需要交换，保证大堆的特性if (arr[child] > arr[parent]){swap(&arr[child], &arr[parent]);//继续向下调整parent = child;child = parent * 2 + 1;}else{//如果孩子结点小于父结点，说明不需要调整了，跳出循环break;}}}void HeapPop(Heap* heap)//删除堆顶数据
{assert(heap);assert(heap->size>0);//先将堆顶的元素和最后一个元素进行交换swap(&heap->arr[0], &heap->arr[heap->size - 1]);//堆数据个数-1heap->size--;//向下调整AdjustDown(heap->arr,heap->size,0);
}

上面已经给出了代码和交换的图片，我们首先来讲一下为什么需要通过交换才能删除这个最大（最小）元素，究其原因还是它在根节点的原因，没有办法对它进行一个直接删除，一旦直接删除，就会导致整体的一个堆结构就乱掉了。我们根结点的左子树和右子树是堆，不能破坏它，那么最好的方法就是和尾元素进行交换，然后进行向下调整，这样不但保证了结构的完整性，效率还高。
向下调整如下图:

2.2.7.堆的判空

bool HeapEmpty(Heap* heap)//堆是否为空
{assert(heap);return heap->size == 0;
}

2.2.8.堆的数据个数

int HeapSize(Heap* heap)//堆的数据个数
{assert(heap);return heap->size;
}

2.2.9.交换

void swap(T* x, T* y)//交换
{T tmp = *x;*x = *y;*y = tmp;
}

2.2.10.打印堆数据

void HeapPrint(Heap* heap)//将堆数据打印出来
{for (int i = 0; i < heap->size; ++i){printf("%d ", heap->arr[i]);}printf("\n");
}

2.2.11.堆的创建

//简单粗暴的一种方法
void HeapCreate1(Heap* heap, T* a, int n)//创建堆1
{assert(heap);HeapInit(heap);for (int i = 0; i < n; i++){HeapPush(heap, a[i]);}
}void AdjustDown(T* arr, int size, int parent);//定义在下面，这边要使用，声明一下void HeapCreate2(Heap* heap, T* a, int n)//创建堆2
{assert(heap);HeapInit(heap);//开辟空间heap->arr = (T*)malloc(sizeof(T) * n);if (heap->arr == NULL){perror("malloc fail");exit(-1);}//拷贝数据memcpy(heap->arr, a, n*sizeof(T));heap->size = heap->capacity = n;//从下至上进行向下调整for (int end = (n - 1 - 1) / 2; end >= 0; end--){AdjustDown(heap->arr, n, end);}
}

上面展示了代码和图片，堆的创建我们用了两种方法，第一种就比较直接，循环push即可，但它的效率不是很高，于是我们有了第二种方法，想要保证一组毫无序列的元素变成堆，就需要保证每一个子树的父节点都大于（小于）孩子节点，因此我们只能从最后一棵子树开始向下调整（叶子结点不需要调整了），这样当调整到上一层时，下层都已经是堆了，只需要对当前节点也是向下调整即可。一直到根节点完成最后一次向下调整就可以完成堆的构建。
在代码中end两次-1，第一次-1是为了找到最后一个元素在数组中的位置，第二次-1是为了找到父结点。

2.2.12.堆排序

在我们讲述堆排序前，我们先来讨论一下，当我们对于一个随机的数组，将它变成一个堆，是使用向上调整好还是向下调整好呢？我们接下来分析一下



可以看到，向下调整和向上调整都能建堆，如果简单来看的话会认为向上调整的时间复杂度是都是O(N*logN)，而向下调整就有点难以看出来了，我们来计算一下

我们的向下调整在前面的代码中已经演示过了，它从最后一个结点的父结点开始调整，并且我们要验证它的时间复杂度就得使用最坏的情况，就是满二叉树。根据上图的详细计算可以得出向下调整的时间复杂度是O(N)
接下来再来看一下，向上调整的时间复杂度计算

上图为向上调整的计算过程，通过规律，我们很快就算了出来，可以发现向上调整的时间复杂度是O(N *log₂N)。其实我们仔细观察一下，可以发现我们的向上调整次数其实都是聚集在最后一层，最后一层不但结点是整棵二叉树中最多的，调整次数也是最多的；反观向下调整中，结点越是在上面，调整次数越多，但结点越少，反倒是最后一层，并没有进行调整，这就是造成两者时间复杂度差距的原因，因此我们在选择调整时，优先选择向下调整

void HeapSort(int* arr,int n)//堆排序
{//向上调整--O(N*logN)/*for (int i = 0; i < n; i++){AdjustUp(arr, i);}*///向下调整--O(N)for (int i =(n-1-1)/2; i>=0; i--){AdjustDown(arr, n,i);}//堆排序-升序-使用大堆int end = n-1;while (end > 0)//当end==0时说明调整结束{swap(&arr[0],&arr[end]);AdjustDown(arr, end, 0);end--;}}

接下来就可以看我们的堆排序的代码和图片，其中我们升序时需要使用大堆，降序时使用小堆，我们通过交换+向下调整，将数据依次从数组尾部开始放，这其实就是借鉴了我们的将堆内的top数据取出再pop的思想，并且我们的这个排序只需要写向下调整的代码即可，不需要完整的把堆代码写完。
我们可以看一下如果使用top+pop函数也能达到类似排序效果


我们接下来再看一下堆排序的时间复杂度

经过上面的分析，就可以知道一开始建堆向下调整的时间复杂度是O(N)，循环交换+向下调整的时间复杂度是O(N*log₂N)，那么根据时间复杂度的计算方式，堆排序的时间复杂度为O(N*log₂N)

2.2.13.完整代码

//Heap.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>
typedef int T;//堆数据类型typedef struct Heap
{T* arr;//堆的存储位置int size;//堆的数据个数int capacity;//堆的容量
}Heap;void HeapInit(Heap* heap);//堆的初始化
void HeapCreate1(Heap* heap, T* a, int n);//创建堆方法1
void HeapCreate2(Heap* heap, T* a, int n);//创建堆方法2
void HeapDestory(Heap* heap);//将堆销毁
void HeapPush(Heap* heap,T x);//堆的构建
void HeapPrint(Heap* heap);//将堆数据打印出来
T HeapTop(Heap* heap);//取出堆顶数据
void HeapPop(Heap* heap);//删除堆顶数据
int HeapSize(Heap* heap);//堆的数据个数
bool HeapEmpty(Heap* heap);//堆是否为空void swap(T* x, T* y);//交换
void AdjustUp(T* arr, int child);//向上调整
void AdjustDown(T* arr, int size, int parent);//向下调整void HeapSort(int* arr,int n);//堆排序

//Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
void HeapInit(Heap* heap)//堆的初始化
{assert(heap);heap->arr = NULL;heap->capacity = heap->size = 0;
}//简单粗暴的一种方法
void HeapCreate1(Heap* heap, T* a, int n)//创建堆1
{assert(heap);HeapInit(heap);for (int i = 0; i < n; i++){HeapPush(heap, a[i]);}
}void AdjustDown(T* arr, int size, int parent);//定义在下面，这边要使用，声明一下void HeapCreate2(Heap* heap, T* a, int n)//创建堆2
{assert(heap);HeapInit(heap);//开辟空间heap->arr = (T*)malloc(sizeof(T) * n);if (heap->arr == NULL){perror("malloc fail");exit(-1);}//拷贝数据memcpy(heap->arr, a, n*sizeof(T));heap->size = heap->capacity = n;//从下至上进行向下调整for (int end = (n - 1 - 1) / 2; end >= 0; end--){AdjustDown(heap->arr, n, end);}
}void HeapDestory(Heap* heap)//将堆销毁
{assert(heap);free(heap->arr);//释放空间heap->size = heap->capacity = 0;
}void swap(T* x, T* y)//交换
{T tmp = *x;*x = *y;*y = tmp;
}//我们默认建立大堆哈
void AdjustUp(T* arr,int child)//向上调整
{int parent = (child - 1) / 2;//找父结点//使用parent>=0有点不合理，倒数第二次运行循环时child已经是0了，应该结束//但是（child-1）/2导致parent依旧为0，再次进入循环，然后通过else中的breakwhile (child>0){//孩子结点大于父结点if (arr[child] > arr[parent]){//交换swap(&arr[child], &arr[parent]);//继续向上调整child = parent;parent = (child - 1) / 2;}else{//如果孩子结点小于父结点，就不用向上调整了break;}}
}void HeapPush(Heap* heap, T x)//堆的插入
{assert(heap);//空间不足开辟内存if (heap->size == heap->capacity){int newcapacity = heap->capacity == 0 ? 4 : heap->capacity * 2;//realloc的第一个元素是NULL的话，功能和malloc一样T* newarr = (T*)realloc(heap->arr, newcapacity*sizeof(T));if (newarr == NULL){perror("realloc fail");exit(-1);}//修改已经开辟好空间后的信息heap->arr = newarr;//realloc可能不在原位扩容，所以说这一步是必要的heap->capacity = newcapacity;}//正式插入heap->arr[heap->size] = x;heap->size++;//数据个数+1//向上调整，保证是一个堆AdjustUp(heap->arr, heap->size - 1);
}void HeapPrint(Heap* heap)//将堆数据打印出来
{for (int i = 0; i < heap->size; ++i){printf("%d ", heap->arr[i]);}printf("\n");
}T HeapTop(Heap* heap)//取出堆顶数据
{	assert(heap);assert(heap->size > 0);return heap->arr[0];
}void AdjustDown(T* arr, int size,int parent)
{//选出左孩子和右孩子中较大的那个//假设较大的是左孩子int child = parent * 2 + 1;//孩子结点存在才向下调整while (child<size){if (child + 1 < size && arr[child + 1] > arr[child]){//进行判断，如果右孩子大于左孩子，就+1，因为左孩子和右孩子之间就相差1child++;}//孩子结点大于父节点，就需要交换，保证大堆的特性if (arr[child] > arr[parent]){swap(&arr[child], &arr[parent]);//继续向下调整parent = child;child = parent * 2 + 1;}else{//如果孩子结点小于父结点，说明不需要调整了，跳出循环break;}}}void HeapPop(Heap* heap)//删除堆顶数据
{assert(heap);assert(heap->size>0);//先将堆顶的元素和最后一个元素进行交换swap(&heap->arr[0], &heap->arr[heap->size - 1]);//堆数据个数-1heap->size--;//向下调整AdjustDown(heap->arr,heap->size,0);
}int HeapSize(Heap* heap)//堆的数据个数
{assert(heap);return heap->size;
}bool HeapEmpty(Heap* heap)//堆是否为空
{assert(heap);return heap->size == 0;
}void HeapSort(int* arr,int n)//堆排序
{//向上调整--O(N*logN)/*for (int i = 0; i < n; i++){AdjustUp(arr, i);}*///向下调整--O(N)for (int i =(n-1-1)/2; i>=0; i--){AdjustDown(arr, n,i);}//堆排序-升序-使用大堆int end = n-1;while (end > 0)//当end==0时说明调整结束{swap(&arr[0],&arr[end]);AdjustDown(arr, end, 0);end--;}}

//main.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
//验证Push能否正常工作
void Test1()
{Heap heap;HeapInit(&heap);int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };for (int i = 0; i < sizeof(array) / sizeof(T); i++){HeapPush(&heap,array[i]);}HeapPrint(&heap);
}//验证能否正常使用Pop并模拟排序
void Test2()
{Heap heap;HeapInit(&heap);int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };for (int i = 0; i < sizeof(array) / sizeof(T); i++){HeapPush(&heap, array[i]);}HeapPrint(&heap);for (int i = 0; i < sizeof(array) / sizeof(T); i++){	printf("%d ", HeapTop(&heap));HeapPop(&heap);}printf("\n");
}//验证Create
void Test3()
{Heap heap;int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };HeapCreate2(&heap,array,sizeof(array)/sizeof(int));HeapPrint(&heap);for (int i = 0; i < sizeof(array) / sizeof(T); i++){printf("%d ", HeapTop(&heap));HeapPop(&heap);}printf("\n");
}//验证堆排序
void Test4()
{Heap heap;int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };HeapSort(array, sizeof(array) / sizeof(int));for (int i = 0; i < sizeof(array) / sizeof(int); i++){printf("%d ", array[i]);}
}int main()
{Test3();return 0;
}

3.Top-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
① 总共N个数据，用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
② 设求前K个最大的元素，建小堆，用剩余的N-K个元素依次与堆顶元素来比较，比堆顶大的就替换，然后进行向下调整
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素

//Top-K问题
#include <stdio.h>
#include <stdlib.h>
#include <time.h>void swap(T* x, T* y)//交换
{T tmp = *x;*x = *y;*y = tmp;
}void AdjustDown(T* arr, int size, int parent)
{//选出左孩子和右孩子中较小的那个//假设较小的是左孩子int child = parent * 2 + 1;//孩子结点存在才向下调整while (child < size){if (child + 1 < size && arr[child + 1] < arr[child]){//进行判断，如果右孩子小于左孩子，就+1，因为左孩子和右孩子之间就相差1child++;}//孩子结点小于父节点，就需要交换，保证小堆的特性if (arr[child] < arr[parent]){swap(&arr[child], &arr[parent]);//继续向下调整parent = child;child = parent * 2 + 1;}else{//如果孩子结点大于父结点，说明不需要调整了，跳出循环break;}}}int  main()
{int  k = 5;//求Top-10int n = 20;//数据数量srand((unsigned)time(NULL));//1.生成一堆随机数写入文件中//1.1打开文件FILE* fin = fopen("data.txt", "w");int flag = k;//1.2写入for (int i = 0; i < n; i++){//i%3保证是随机添加，而不是连续，flag保证添加了k个if (i % 3 == 0 && flag-- > 0){//1.3方便测试，添加几个大于等于10000的数据fprintf(fin, "%d\n", 10000+i);}else{fprintf(fin, "%d\n", rand() % 10000);}}//1.4关闭文件fclose(fin);//2.建立小堆//2.1开辟空间int* array = (int*)malloc(sizeof(int) * k);//2.2向下调整for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(array, n, i);}//3.用剩余的N-K个元素依次与堆顶元素来比较，比堆顶大的就替换，然后进行向下调整//3.1打开文件FILE* fout = fopen("data.txt", "r");//3.2从文件读取int value = 0;while (fscanf(fout, "%d", &value) != EOF){//3.3和堆顶进行比较if (array[0] < value){array[0] = value;//3.4向下调整AdjustDown(array, k, 0);}}//3.4关闭文件fclose(fout);//4.验证结果//10000 10006 10003 10009 10012for (int i = 0; i < k; i++){printf("%d ", array[i]);}printf("\n");return 0;
}

它的时间复杂度的计算过程：前面讲的向下调整的建堆过程的时间复杂度是O(N)，N是结点个数，那么代入到这，K也是结点个数(数组大小)，那么建堆过程的复杂度为O(K);还需要比较+向下调整，堆的大小是K，需要调整次数为log₂K-1(-1不包含自己层，并且这里的log₂K是比较精确的，不像前面排序会改变end，导致每次调整时间复杂度逐渐减小)，时间复杂度是O(log₂K)，需要比较N-K次，那么总的时间复杂度就是(N-K) * log₂K。综上所述，K+(N-K) * log₂K=>Top-K时间复杂度为O(N*log₂K)，空间复杂度是O(K)，这个空间K是存放堆的数据的
假设有100亿整数的数据，找Top10，那么就需要100亿*4byte=400亿byte=40G(1G=1024 *1024 *1024byte≈10亿byte)，对于现在的电脑来说40G还是不现实，如果以后真有了，就可以建立一个N个数的大堆，Pop个K次，依次取堆顶，那么它的时间复杂度就为O(N+log₂N *K)， 建堆需要O(N)，K个数据需要向下调整log₂N，这其实和堆排序的时间复杂度计算方式差不多，只是向下调整K次和全部调整的区别。
其实如果真的能够实现40G的内存的话，两个的时间复杂度差不多，O(N *log₂K)忽略log₂K，O(N+log₂N *K)忽略log₂N *K，都是O(N)，在N这个大数量级上其实也是可以忽略的！

🌸🌸二叉树-堆的知识大概就讲到这里啦，博主后续会继续更新更多数据结构的相关知识，干货满满，如果觉得博主写的还不错的话，希望各位小伙伴不要吝啬手中的三连哦！你们的支持是博主坚持创作的动力！💪💪