二叉树顺序结构以及实现
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费，因此完全二叉树更适合使用顺序结构来存储。
二叉树一般有两种结构存储: 顺序结构和链式结构。
顺序结构也就是顺序表(数组)来存储，一般只有完全二叉树和满二叉树适合数组来存储。其他二叉树会有空值——会造成空间浪费。而我们通常把堆(一种二叉树)使用顺序结构的数组来存储。
二叉树顺序存储在物理上是一个数组，在逻辑上(想象中的)是一颗二叉树。
小堆：每个父亲都小于等于孩子 parent<=child
大堆：每个父亲都大于等于孩子 parent>=child
leftchild=parent*2+1 rightchild=parent*2+2
那么parent怎么计算呢？推导一下即可
parent=(child-1)/2;
小堆(举例)
如果插入一个数据元素90 直接尾插即可 顺序表尾插效率高，而且没有破坏小堆的结构。
如果插入一个数据元素55呢？求出父亲是60
从上面情况可以看出有两种情况
1.直接插入不会影响原来堆的结构 直接尾插即可。
2.插入数据会出现比父亲小的情况(小堆)，这时候就需要去调整堆的关系，才能形成正确的堆关系，好的情况下一次调整就完成了调整，那么最坏的情况就是调整到根节点才会结束调整。
就比如下面这种情况，尾插的数据元素5直接从孙子变成了太爷爷
把数组中最后一个数据元素作为孩子，根据孩子求出父亲位置，再判断孩子是否小于父亲，如果符合条件就调整位置，再把父变子，再求父亲位置，循环以上步骤，最坏判断到根节点。
怎么判断循环结束条件呢？根据上面的画图，不难看出当parent<0 循环就结束了，但不能这样判断，因为当parent为0时 -1/2还是0 因为是除 余为0。在我们画图分析时，parent看起来会往上走，但实际还是0，因此我们要以孩子作为循环执行条件，从上面画图分析可以看出child>0时循环执行，当child==0时循环结束，因此循环执行条件应该是child>0。
说了那么多理论知识和方法，接下来开始写代码。
向上调整
void Adjustup(Heapdatatype* a, int child)
{
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;
}
}
}向上调整的前提：数据是堆
如果插入数据不符合条件break跳出循环即可
那么向下调整的时间复杂度是多少呢？深度为h的二叉树最大结点为2^h-1，假设有N个数据
那么时间复杂度就是O(logN) 如果有10亿数据也只需调整30次。
堆删除数据
那么如果堆要删除数据，怎么删呢？直接尾删吗？
把70删掉并没有实际意义，把根节点删掉才有意义
挪动覆盖大概率会打乱堆的之间的关系——形不成堆。
那么怎么删除呢？前辈研究发现结果是——先把根节点和最后一个结点先交换，再删除
通过根节点和最后一个结点数据交换再删除，可以发现左右子树都没有被动到，左右子树依旧是小堆。但"爷爷"隐退江湖，给孙子让位当掌门，底下的其他人坐得住吗？显然是坐不住的，因此要进行比武大会，打赢的人才有资格当下一个掌门人。
经过一系列的比武，70不出所料的又到最下面去了，德不配位了属于是。
因此向下调整的前提是：左右子树是大堆/小堆
时间复杂度也是log(N)
向下调整怎么写呢？大部分人都会先比较左右孩子(小堆为例,找出最小孩子)，再上去调整，但这样写太麻烦了，不太推荐
向下调整
void AdjustDown(Heapdatatype*a,int n,int parent)
{
int child = parent * 2 + 1;//默认左孩子最小
while (child<n)
{
//如果假设左孩子小了是错误的 就再判断一次(找出最小孩子)
if (a[child + 1] < a[child])
{
++child;
}
//光标闪动之处就是最小孩子位置//最小孩子 不关心是左/右子
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}我们演示的是小堆的向下调整，因此我们先默认左孩子是最小的孩子，但我们的判断可能会出错误，因此在循环里面再判断一次 ，判断完成后，光标闪动的地方就是最小孩子的位置(我们不关心是左孩子最小还是右孩子最小，找出最小孩子即可)，再跟向上调整一样，判断父子之间的关系，进行调整。
从画图可以看出当child大于size循环结束，因此循环继续条件就是child小于n。
向下调整存在的问题
大家继续看看这段代码有什么bug吗？ 有的
万一右孩子不存在呢？如果右孩子不存在,child++就越界了，因为在判断条件还要补上右孩子是存在的条件。
实验代码
int main()
{
int arr[] = { 65,100,70,32,50,60 };
Hp ph;
HpInit(&ph);
for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
//push进去以后才是堆 大堆还是小堆 具体看调整符号
//我们建的是小堆
HpPush(&ph,arr[i]);
}
HpPrint(&ph);
//int k = 5;//取前5个最大的 k--走k次 --k走k-1次
while (!HpEmpty(&ph))
{
printf("%d ", HpTop(&ph));
HpPop(&ph);
}
HpDestroy(&ph);
return 0;
}当push进去向上调整后，成为小堆以后，取栈顶元素再pop后，小堆变成了有序
当是大堆时，大堆变成了降序
大堆可以依次排出降序 小堆可以依次排出升序
但注意，目前还不算堆排序，
如果有100家外卖店，要排出了前10个最高评分的店，是不是topk问题？根本不用一个个比较，直接把数据push进去(建堆)，再不断Top pop就可以依次取出最高/最小元素排列顺序。
如果要取出前5个最大的 直接设一个变量 再--就可以取出来
堆排序
void HeapSort(int* a, int n)
{
Hp ph;
HpInit(&ph);
for (size_t i = 0; i <n; i++)
{
HpPush(&ph,a[i]);
}
//HpPrint(&ph);不需要这步
int i = 0;
while (!HpEmpty(&ph))
{
//printf("%d ", HpTop(&ph));
a[i++] = HpTop(&ph);//直接覆盖
HpPop(&ph);
}
HpDestroy(&ph);
return 0;
}堆排序存在问题
这个堆排序有什么缺陷呢?
1.首先我们得有个数据结构，把结构体 destroy push之类的构建出来，而且人家只需要堆排序以后的结果，不需要我们打印大堆/小堆数据，那么我们直接建立个新数组直接把堆排序结果覆盖进去。
2. 空间复杂度的消耗，数据结构申请了空间资源，因为排序额外开了新的数据空间，造成了二次空间数据空间浪费。
正确的堆排序
怎么改善堆排序呢？
直接在原数组上建堆(实际上是插入)
向上调整建堆
向上建堆的时间复杂度O(N*logN)
void HeapSort(int* a, int n)
{
int i = 0;
for (i = 1; i < n; i++)
{
Adjustup(a, i);
}
}
直接在原数组上建堆，省去了push的申请空间资源，节省了空间浪费。
如果我们要建升序 是建小堆还是大堆
如果要升序建小堆
选出了最小的数据，要选次小，只能把剩下的数据看做堆
但关系全乱了，剩下的数据不一定是堆，要重新建堆，建堆代价太大 时间复杂度为(N*log(N))*N
因此如果要建升序 最好是建大堆+删除思想
首尾交换 最大的数据排好了，剩下的数据向下调整，选出次大的即可。
时间复杂度是N*log(N)
向下调整建堆
向下建堆时间复杂度是O(N)
向下调整建堆会根据不同情况 有不同数据排序变化
大堆时是升序 小堆是降序 向上调整建堆一样。
因此在建堆时，向下调整建堆优势于向上调整建堆。
TopK问题
Topk问题：就是求出数据中前k个最大或最小的元素，一般情况下数据量比较大。
比如:一个游戏内全服最强前10名玩家、世界500强公司等等......
对于TopK问题，最简单的办法就是排序，建个小堆或者大堆 不断取出堆顶数据然后pop数据 就可以排出来 前k个最大或最小的元素数据(在数据量少时)，但在数据量比较大时，将所有数据全部加入内存再进行排序是不太可能的，会超过电脑本身的内存空间，造成大量的空间浪费。
因此我们就想出一下办法，在大量数据中排出前k个最大元素。
假设10亿个数据，内存存不下，数据在文件中找出最大的前K个 K==100
1.读取文件的前100个数据，在内存数组中建立一个小堆
2、再依次读取剩下数据，跟堆顶数据比较，大于堆顶，就替换它进堆，向下调整
3、所有数据读完，堆里面数据就是最大的前100个
为什么求出前k个最大元素要建小堆？如果建立大堆，如果在N个元素中，最大的元素数据第一个就来了进堆顶，只能找出最大的一个元素，其他比它小的元素数据将进不了堆，因此不能建大堆。
而且建小堆，当我们把前100个数据元素建立好堆后，剩下的前k个最大数据元素都能进堆，因为是小堆，不会出现占在栈顶 不让其他数据元素进堆的情况，因为会向下调整。
因此Topk的空间复杂度和时间复杂度都很优秀。
时间复杂度是O(N*logK) 空间复杂度是O(K) 但这种情况都是N大于K K都可以忽略不计
因此空间复杂度可以是O(1) 时间复杂度O(N)
Topk数据测试
void CreateNDate()
{
// 造数据
int n = 10000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
int x = rand() % 1000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
int main()
{
CreateNDate();
}创造了10000个数据
void PrintTopK(const char*filename, int k)
{
// 1. 建堆--用a中前k个元素建堆
FILE* fout = fopen(filename, "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL)
{
perror("malloc fail");
return;
}
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minheap[i]);
}
//前k个数建小堆
for (int i = (k - 2) / 2; i >= 0; --i)
{
AdjustDown(minheap, k, i);
}
// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
if (x > minheap[0])
{
// 替换你进堆
minheap[0] = x;
AdjustDown(minheap, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minheap[i]);
}
printf("\n");
free(minheap);
fclose(fout);
}
void CreateNDate()
{
// 造数据
int n = 10000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
int x = rand() % 1000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
int main()
{
//CreateNDate();
PrintTopK("data.txt", 10);
}但是，我们怎么知道这10个数据就是10万个数据中最大的10个数据呢？
我们可以在data.txt可以自己去修改随机10个数字，让他大于10万即可，再运行程序，看看结果是不是我们修改的那10个数字就可以了。
完全代码展示
Heap.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
typedef int Heapdatatype;
typedef struct Heap
{
Heapdatatype* _a;
int _capacity;
int _sz;
}Hp;
void Swap(Heapdatatype* p1, Heapdatatype* p2);
void HpInit(Hp* ps);
void HpDestroy(Hp* ps);
void HpPush(Hp* ps, Heapdatatype x);
void HpPrint(Hp* ps);
void HpPop(Hp* ps);
bool HpEmpty(Hp* ps);
Heapdatatype HpTop(Hp* ps);
void AdjustDown(Heapdatatype* a, int n, int parent);
void Adjustup(Heapdatatype* a, int child);
void HpAryy(Hp* ps, int* a, int n);Heap.c
#include"Heap.h"
void HpInit(Hp* ps)
{
assert(ps);
ps->_a = NULL;
ps->_capacity = ps->_sz = 0;
}
void HpDestroy(Hp* ps)
{
free(ps->_a);
ps->_a = NULL;
ps->_capacity = ps->_sz == 0;
}
void HpPrint(Hp* ps)
{
assert(ps);
for (size_t i = 0; i < ps->_sz; i++)
{
printf("%d ", ps->_a[i]);
}
printf("\n");
}
void Swap(Heapdatatype* p1, Heapdatatype* p2)
{
Heapdatatype tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void Adjustup(Heapdatatype* a, int child)
{
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;
}
}
}
void HpPush(Hp* ps, Heapdatatype x)
{
assert(ps);
if (ps->_sz == ps->_capacity)
{
int newcapcity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
Heapdatatype* tmp = (Heapdatatype*)realloc(ps->_a, sizeof(Heapdatatype) * newcapcity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->_a = tmp;
ps->_capacity = newcapcity;
}
ps->_a[ps->_sz] = x;
ps->_sz++;
Adjustup(ps->_a, ps->_sz - 1);
}
void AdjustDown(Heapdatatype*a,int n,int parent)
{
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;
}
}
}
void HpAryy(Hp* ps, int* a, int n)
{
assert(ps);
assert(a);
ps->_a = (Heapdatatype*)malloc(sizeof(Heapdatatype) * n);
if (ps->_a == NULL)
{
perror("malloc fail");
return;
}
ps->_sz = n;
ps->_capacity = n;
memcpy(ps->_a, a, sizeof(Heapdatatype) * n);
for (int i = 1; i < n; i++)
{
Adjustup(ps->_a, i);
}
}
void HpPop(Hp* ps)
{
assert(ps);
assert(ps->_sz > 0);
Swap(&ps->_a[0], &ps->_a[ps->_sz - 1]);
ps->_sz--;
AdjustDown(ps->_a,ps->_sz,0);
}
bool HpEmpty(Hp* ps)
{
assert(ps);
return ps->_sz == 0;
}
Heapdatatype HpTop(Hp* ps)
{
assert(ps);
assert(ps->_sz > 0);
return ps->_a[0];
}test.c
#include"Heap.h"
#include<time.h>
//缺陷 1.首先得有一个堆的数据结构 2.空间复杂度的消耗 因为排序额外开了一段空间
//void HeapSort(int* a, int n)
//{
// Hp ph;
// HpInit(&ph);
// for (size_t i = 0; i <n; i++)
// {
//
// HpPush(&ph,a[i]);
// }
// //HpPrint(&ph);
// //堆排要的是排序结果 不用你把原来数据打印
// int i = 0;
// while (!HpEmpty(&ph))
// {
// //printf("%d ", HpTop(&ph));
// a[i++] = HpTop(&ph);//直接覆盖
//
// HpPop(&ph);
// }
// HpDestroy(&ph);
// return 0;
//}
//为什么向上调整和向下调整传的不是hp 而是数组的结构 就是为了方便这里的建堆
void HeapSort(int* a, int n)
{
//int i = 0;
//建堆-向上调整
//建升序 是大堆还是小堆？
//大堆
//for (i = 1; i < n; i++)//N*log(N)
//{
// Adjustup(a, i);
//}
//向下调整建堆—大堆
//时间复杂度O(logN)
int i = 0;
for (i = (n - 1 - 1) / 2; i >=0; i--)
{
AdjustDown(a, n, i);
}
//O（N*logN）
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
int main()
{
//随便一个数组可以看成是二叉树 但不可能是堆 所以要先建堆
int arr[] = { 65,100,70,32,50,60 };
Hp ph;
HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
int i = 0;
for (i = 0; i < 6; i++)
{
printf("%d ", arr[i]);
}
}
//int main()
//{
// int arr[] = { 65,100,70,32,50,60 };
// Hp ph;
// HpInit(&ph);
// for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
// {
// //push进去以后才是堆 大堆还是小堆 具体看调整符号
// HpPush(&ph,arr[i]);
// }
// HpPrint(&ph);
//
// int k = 5;//取前5个最大的 k--走k次 --k走k-1次
// while (!HpEmpty(&ph)&&k--)
// {
// printf("%d ", HpTop(&ph));
// HpPop(&ph);
// }
//
// HpDestroy(&ph);
// return 0;
//}
//void PrintTopK(const char*filename, int k)
//{
// // 1. 建堆--用a中前k个元素建堆
// FILE* fout = fopen(filename, "r");
// if (fout == NULL)
// {
// perror("fopen fail");
// return;
// }
//
// int* minheap = (int*)malloc(sizeof(int) * k);
// if (minheap == NULL)
// {
// perror("malloc fail");
// return;
// }
//
// for (int i = 0; i < k; i++)
// {
// fscanf(fout, "%d", &minheap[i]);
// }
//
// //前k个数建小堆
// for (int i = (k - 2) / 2; i >= 0; --i)
// {
// AdjustDown(minheap, k, i);
// }
//
// // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
// int x = 0;
// while (fscanf(fout, "%d", &x) != EOF)
// {
// if (x > minheap[0])
// {
// // 替换你进堆
// minheap[0] = x;
// AdjustDown(minheap, k, 0);
// }
// }
//
//
// for (int i = 0; i < k; i++)
// {
// printf("%d ", minheap[i]);
// }
// printf("\n");
//
// free(minheap);
// fclose(fout);
//}
//
//
//void CreateNDate()
//{
// // 造数据
// int n = 10000;
// srand(time(0));
// const char* file = "data.txt";
// FILE* fin = fopen(file, "w");
// if (fin == NULL)
// {
// perror("fopen error");
// return;
// }
//
// for (int i = 0; i < n; ++i)
// {
// int x = rand() % 1000000;
// fprintf(fin, "%d\n", x);
// }
//
// fclose(fin);
//}
//
//int main()
//{
// //CreateNDate();
// PrintTopK("data.txt", 10);
//}