树的完整概念与堆的深度剖析

`#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//如何表示一个树呢（代码实现如何定义结构）
//法1.假设说明了树的度是N（最大是这么多）
struct treenode
{
  int data;
  struct treenode*subs[N];//这个数组是一个指针数组，里面存的都是指针，但是有缺陷，问题在于
  //1.可能会存在不少空间的浪费，如假设只有一个树的度是8，其余的都是0，1，2……浪费了很多空间
  //万一没有给我们树的度为多少呢，
};
//法2；
//假设我们已经定义了一个顺序表seqlist出来了，数据类型是
//typedef struct treenode* seqdata
//这个顺序表里面存的是节点的指针
//struct treenode
//{
//  int data;
//  seqlist s;//
//};
//法3.结构数组村粗
//struct treenode
//{
//  int parenti;
//  int data;
//
//};
//上面的方式各有优缺点，表示树结构的最优方法，  使用左孩子右兄弟表示法
typedef int datatype;
struct node
{
  struct node*firstchild;//第一个孩子节点，    永远指向第一个孩子
  struct node*pnextbrother;//指向下一个兄弟节点  指向孩子右边的兄弟
  datatype data;   //节点中的数据域
};
//二叉树
//不学习他的增删查改，没有意义
//而是去控制一下他的结构（高度，深度）
//作用是搜索二叉树：用来进行查找，-》平衡搜索二叉树，（avl树和红黑树，b树）（这些结构才会去学习他的增删查改）

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//堆是一个完全二叉树
//我们已经推导了公式，已知父亲，左为父*2+1，右为父*2+2
//已知孩子，父亲为（子-1）/2
typedef int hpdata;
typedef struct heap
{
  //物理结构就是一个顺序表
  hpdata *a;
  int size;
  int capacity;
}heap;
//初始化
void heapinit(heap* hp);
// 销毁
void heapdestroy(heap* hp);
//插入
void heappush(heap *hp, hpdata x);
//删除
void heappop(heap*hp);
void adjustup(hpdata *a, int n, int child);
void heapprint(heap*hp);
//判空
bool heapempty(heap*hp);
int heapsize(heap*hp);
//
void swap(hpdata*x, hpdata*y);
//向下调
void adjustdown(int *a, int size, int parent);

#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
//初始化
void heapinit(heap* hp)
{
  assert(hp);
  hp->capacity =hp->size= 0;
  hp->a = NULL;
}
// 销毁
void heapdestroy(heap* hp)
{
  assert(hp);
  free(hp->a);
  hp->a = NULL;
  hp->capacity = hp->size = 0;
}
//向上调整
void adjustup(hpdata *a, int n, int child)//a就是这数组，n就这个数组右多大
{
  assert(a);
  int parent = (child - 1) / 2;
  //while(parent>=0)
  while (child >0)//调到根
  {
    if (a[child] > a[parent])//大于就交换
    {
      //交换
      hpdata tmp = a[child];
      a[child] = a[parent];
      a[parent] = tmp;
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;//小于就停止
    }
  }
}
//插入
//假设是大堆
void heappush(heap *hp, hpdata x)
{
  assert(hp);
  //满了就要先增容
  if (hp->size == hp->capacity)
  {
    size_t newcapcity = hp->capacity == 0 ? 4 : hp->capacity * 2;
    hpdata *tmp = (hpdata*)realloc(hp->a, sizeof(hpdata)*newcapcity);
    if (tmp != NULL)
    {
      hp->a = tmp;
      hp->capacity = newcapcity;
    }
    else
    {
      perror("realloc");
      return;
    }
  }
  hp->a[hp->size] = x;
  hp->size++;
  adjustup(hp->a, hp->size, hp->size-1);
}
void heapprint(heap*hp)
{
  int i = 0;
  for (i = 0; i < hp->size; i++)
  {
    printf("%d ", hp->a[i]);
  }
}
```c
bool heapempty(heap*hp)
{
  assert(hp);
  return hp->size == 0;//为0就是空的，不为0就不是空的
}
int heapsize(heap*hp)
{
  assert(hp);
  return hp->size;
}
//向上调的时间复杂度是
//
//向上调高度次
void adjustdown(int *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;
    }
  }
}
//删除
//再堆里面删除不是随便任意删除什么位置都可以
//而是删除堆顶的数据（根），意义是调整堆，找到次小的值（小堆）
//向下调整，把他调整成堆，跟左右孩子中小的那个交换
//结束条件
//1.父亲<=小的那个孩子，则停止
//2.调整到叶子（当父亲走到叶子就停止，叶子是没有左孩子，左孩子下标超出数组范围就不存在）
void heappop(heap*hp)
{
  assert(hp);
  assert(!heapempty(hp));//空了就别删除了
  //先把堆顶和底部删掉
  swap(&hp->a[0], &hp->a[hp->size - 1]);
  hp->size--;//删掉了
  //交换之后，向下调整，保证不破坏堆,从0开始向下调
  adjustdown(hp->a, hp->size, 0);
}

#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
int main()
{
  int a[] = { 70,56,30,25,15,10,75 };//用数组去给hp值
  heap HP;//定义一个堆
  heapinit(&HP);
  for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
  {
    heappush(&HP, a[i]);
}
  heapprint(&HP);
  return 0;
}

// 在N个数找出最大的前K个  or  在N个数找出最小的前K个
void PrintTopK(int* a, int n, int k)
{
  heap hp;
  heapinit(&hp);
  // 创建一个K个数的小堆
  for (int i = 0; i < k; ++i)
  {
    heappush(&hp, a[i]);//一个一个入堆
  }
  // 剩下的N-K个数跟堆顶的数据比较，比他大，就替换他进堆
  for (int i = k; i < n; ++i)
  {
    if (a[i] > heaptop(&hp))//比较，大的就入堆
    {
      heappop(&hp);//把顶补的删掉，
      heappush(&hp, a[i]);//大的入堆
      //hp.a[0] = a[i];//把顶部的换成现在大的
      //adjustdown(hp.a, hp.size, 0);//向下调整
    }
  }
  heapprint(&hp);
  heapdestroy(&hp);
}
void TestTopk()
{
  int n = 1000000;
  int* a = (int*)malloc(sizeof(int)*n);
  srand(time(0));
  for (size_t i = 0; i < n; ++i)
  {
    a[i] = rand() % 1000000;
  }
  // 再去设置10个比100w大的数
  a[5] = 1000000 + 1;
  a[1231] = 1000000 + 2;
  a[5355] = 1000000 + 3;
  a[51] = 1000000 + 4;
  a[15] = 1000000 + 5;
  a[2335] = 1000000 + 6;
  a[9999] = 1000000 + 7;
  a[76] = 1000000 + 8;
  a[423] = 1000000 + 9;
  a[3144] = 1000000 + 10;
  PrintTopK(a, n, 10);
}
int main()
{
TestTopk();
return 0;
}

//堆排序
//首先先建堆，再应用堆进行排序
//升序就建大堆，降序就建小堆
void HeapSort(int* a, int n)
{
  //法1.
  // 直接把a构建成堆，直接控制a数组，升序，吧
  //把a构建成小堆
  //第一个数先看做堆，后面的数据依次加入堆，然后向上调整，构建堆,调到根就结束了，保证他还是堆
//  if (n <= 1)//第一个就看成堆
//  {
//    return;
//}
  //for (int i = 1; i < n; i++)//后面的数加入进去
  //{
  //  AdjustUp(a,i);
  //}
  //法2；
  //向下调整也可以，保证左子树和右子树都小堆，倒着走最后一个子树进行调整
  //叶子所在的子树不需要调，所以倒着走的第一个非子节点的子树，就是最后一个节点的父亲，调完之后--，直到根 
  //前面的调整为后面做了铺垫，前面调整完之后一定是一个堆
  for (int i = (n - 1-1) / 2; i >= 0; i--)//最后一个位置是n-1，
  {
    AdjustDown(a, n, i);
  }
  //排升序建小堆的分析：
  //1.选出了最小的数放到第一个位置，如何选出次小的位置，只能从第二个位置开始，剩下的数看成一个堆，但是这样的话所有的关系都乱了，只能重新建堆才可以选出次小的堆
  //我们建大堆，最大的数选出来，
  //最大的数放最后一个位置，交换
  //如何选出此校的 数，1.把最后一个数不看做堆里面的了，向下调整就可以选出次小的数，依次内推在重复上面过程，，原本有n个数，现在传n-1个数，就不把他当做堆里面的了
  for (int end = n - 1; end > 0; end--)
  {
    Swap(&a[end], &a[0]);
    AdjustDown(a, end, 0);//向下调整，到根部
  }
}