二叉树-堆（补充）
二叉树-堆
- 1.二叉树的基本特性
- 2.堆
- 2.1.堆的基本概念
- 2.2.堆的实现
- 2.2.1.基本结构
- 2.2.2.堆的初始化
- 2.2.3.堆的销毁
- 2.2.4.堆的插入
- 2.2.5.取出堆顶的数据
- 2.2.6.堆的删除
- 2.2.7.堆的判空
- 2.2.8.堆的数据个数
- 2.2.9.交换
- 2.2.10.打印堆数据
- 2.2.11.堆的创建
- 2.2.12.堆排序
- 2.2.13.完整代码
- 3.Top-K问题
🌟🌟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中的break
while (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，因为左孩子和右孩子之间就相差1
child++;
}
//孩子结点大于父节点，就需要交换，保证大堆的特性
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]);
//堆数据个数-1
heap->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中的break
while (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，因为左孩子和右孩子之间就相差1
child++;
}
//孩子结点大于父节点，就需要交换，保证大堆的特性
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]);
//堆数据个数-1
heap->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，因为左孩子和右孩子之间就相差1
child++;
}
//孩子结点小于父节点，就需要交换，保证小堆的特性
if (arr[child] < arr[parent])
{
swap(&arr[child], &arr[parent]);
//继续向下调整
parent = child;
child = parent * 2 + 1;
}
else
{
//如果孩子结点大于父结点，说明不需要调整了，跳出循环
break;
}
}
}
int main()
{
int k = 5;//求Top-10
int 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 10012
for (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这个大数量级上其实也是可以忽略的！
🌸🌸二叉树-堆的知识大概就讲到这里啦，博主后续会继续更新更多数据结构的相关知识，干货满满，如果觉得博主写的还不错的话，希望各位小伙伴不要吝啬手中的三连哦！你们的支持是博主坚持创作的动力！💪💪