Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。

🌈个人主页：主页链接

🌈算法专栏：专栏链接

我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接

目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

书接上回,本章节也是关于树的内容:二叉树的存储简介,堆的初始化以及应用

1.二叉树的存储结构

相信经过上一阶段的学习(二叉树概念)大家都对二叉树有了一个初步的印象,接下里我们将介绍一下二叉树在内存中一般如何存储.

1.1链式存储

不同于上章所讲的用一个节点存储子结点,另一个节点用来存储兄弟节点,

因为二叉树中的子节点个数是确定的:一个到两个,最多两个.所以我们可以直接创建两个指针记录下其子结点的信息.

二叉链式存储:

就是用两个指针信息来记录其左右子节点的地址.再用一个变量来存储数据.一般是这样写的

typedef int TDatatype;
typedef struct tree
{
    TDatatype val;
    tree *left;
    tree *right;
}tree;

其形象的结构如图所示:

二叉链式存储一般是比较常见的用在二叉树上.但还有一种结构,在后期学习到红黑树会用到的结构

三叉链式存储:

与上方不同,其是用两个指针存储左右儿子,再用一个指针来存储父节点,所以叫做三叉链式存储

typedef int TDatatype;
typedef struct tree
{
    TDatatype val;
    tree *left;
    tree *right;
    tree *parent;
}tree;

其形象的结构如图所示:

1.2顺序存储结构

与链表的相同,二叉树也可以通过数组来存储信息,也就是顺序存储.

如果是二叉树可以用此结构存储,因为其他类型的树使用这种结构会造成大量的空间浪费.

就会出现这种情况

所以不推荐使用

2.堆

2.1堆的性质

先来了解下堆的性质

其本质就是一颗具有特殊属性的完全二叉树

若其父节点都大于等于子节点则称为大顶堆

若其父节点都小于等于子节点则称为小顶堆

下面这些就是大/小顶堆:

2.2堆的数据结构

刚刚提到堆是一颗完全二叉树,那么其结构具有二叉树的顺序存储结构的特点.

typedef int TDataType;
struct tree{
    int size;
    int capacity;
    TDataType *a;
};

其中 size用来存储当前堆中有多少个元素. capacity来判定当前数组是否需要扩容

而a自然是用来存储数据的.这与栈的顺序结构十分相似.

2.3堆的初始化

与链表等结构相同,使用堆前也需要对其初始化.这里没什么好说的,与其他数据结构都相同

void HeapInit(Heap* hp)
{
  hp->size = 0;
  hp->a = (HDataType*)malloc(sizeof(HDataType) * 4);
  if (hp->a == NULL)
  {
    perror("malloc failed");
    return;
  }
  hp->capacity = 4;
}

2.4堆的向上调整

刚刚说过,堆有两种(大顶堆与小顶堆)

想要让一个无序的数组变成这样的,肯定需要对每一个插入的数进行调整.

其中就有向上调整，向下调整两种方式，这里先来讲讲向上调整

将1插入到一个小顶堆，其做的变化如图所示。

先是与父节点比较，父节点(i-1/2)比其大(大顶堆则相反)则交换(不满足小顶堆的规则).

直到child=0时停下

void UpAdjust(HDataType* hp, int child)
{
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    if (hp[parent] > hp[child])
    {
      Swap(&hp[parent], &hp[child]);
      child = parent;
      parent = (parent - 1) / 2;
    }
    else
      break;
  }
}

2.4堆的向下调整

这里介绍下向下调整,向下调整是建一个堆的必要步骤

例如将9插入到一个小顶堆中,需要经历的是这几步

将9的两个子节点进行比较,因为是小顶堆,所以需要挑出其最小的部分,与9进行交换

之后一步步向下调整即可.当child>=n时停止

void DownAdjust(HDataType* hp, int n,int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    if (child+1<n&&hp[child] > hp[child + 1])
    {
      child++;
    }
    if (hp[child] < hp[parent])
    {
      Swap(&hp[child], &hp[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else break;
  }
}

向下调整的效率比向上调整的效率高.这个道理非常的简单,倒数第二层是除叶子节点外最多节点的一层,其向下调整最多只需要调整一层.往上节点越少,调整越多.

而向上调整则刚好相反,第一层节点最少,最多需要调整一次,但最后一层节点最多,需要调整的次数也是最多的.所以一般用向下调整来建堆

2.5堆的插入

有了之前的两个利器,接下来就十分的简单了.

void HeapPush(Heap* hp, HDataType x)
{
  if (hp->size == hp->capacity)
  {
    HDataType* tmp = (HDataType*)realloc(hp->a,sizeof(HDataType) * hp->capacity * 2);
    if (tmp == NULL)
    {
      perror("malloc failed");
      return;
    }
    hp->a = tmp;
    hp->capacity *= 2;
  }
  hp->a[hp->size++] = x;
  UpAdjust(hp->a,hp->size-1);
}

这与栈的插入十分相同,这里就不过多赘述了.值得注意的是最后一步,

UpAdjust的参数为:堆的数组与需要调整的子节点

2.6堆的删除

void HeapDelete(Heap* hp)
{
  if (hp->size <= 0)return;
  Swap(&hp->a[hp->size - 1], &hp->a[0]);
  hp->size--;
  DownAdjust(hp->a, hp->size - 1, 0);
}

首先检查是否为空.

之后交换最后一个数据与第一个数据.将size--,释放最后一段空间,再将刚刚交换的数字进行向下调整

2.7堆的销毁,大小,Empty

这与之前所学相同不过多赘述

需要注意Malloc了多少空间.就要释放多少空间

void HeapDestory(Heap* hp)
{
  free(hp->a);
  hp->capacity = hp->size = 0;
  free(hp);
}
HDataType HeapTop(Heap* hp)
{
  return hp->a[0];
}
int HeapSize(Heap* hp)
{
  return hp->size;
}
int HeapEmpty(Heap* hp)
{
  return hp->size == 0;
}

3.堆排序

其核心仍然是DownAdjust,先通过DownAdjust建一个堆,之后再删除堆顶元素,向下调整,直到size为0

虽然size为0,但是刚刚的数据依照大/小放到最后一位(大小堆决定),所以此时读取数组就变成了有序的.

注意:要排升序需要建大堆(因为大的被放到了最后一个),排降序建小堆

void heapSort(HDataType *a,int n)
{
  /*for (int i = 1; i < n; i++)
  {
    UpAdjust(a, i);
  }*/
  for (int i = (n - 1 - 1 / 2); i >= 0; i--)
  {
    DownAdjust(a, n,i);
  }
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[end], &a[0]);
    end--;
    DownAdjust(a, end,0);
  }
}

因为向下建堆效率更高,所以采用这种方法.

4.TopK问题

给你一个无穷大的数组,想要让你找到前k个最大(最小的数组)如何去找?

十分的简单,先去将这个数组的前十个数据建堆.若找最大的,则建小堆,

将之后的每一个元素都与堆顶元素进行比较(因为堆顶是这十个数中最小的) ,若比他大,则说明堆中至少有一个数(堆顶)需要被换掉,将堆顶等于刚刚这个数,之后执行向下调整即可.

void TopK(const char* f, int top)
{
  int* topk = (int*)malloc(sizeof(int) * top);
  FILE* fl = fopen(f, "r");
  for(int i=0;i<top;++i)
  {
    fscanf(fl, "%d", &topk[i]);
  }
  for (int i = (top-2)/2; i>=0; --i)
  {
    DownAdjust(topk, top, i);
  }
  int val = 0;
  int ret = fscanf(fl, "%d", &val);
  while (ret != EOF)
  {
    if (val > topk[0])
    {
      topk[0] = val;
      DownAdjust(topk, top, 0);
    }
    ret = fscanf(fl, "%d", &val);
  }
  for (int i = 0; i < top; i++)
    printf("%d \n", topk[i]);
  printf("\n");
  free(topk);
  fclose(fl);
}
int main()
{
  const char* f = "data.txt";
  srand(time(NULL));
  FILE* fl = fopen(f, "w");
  for (int i = 0; i < N; i++)
  {
    fprintf(fl, "%d\n", rand() % 10000);
  }
  TopK(f, 10);
  return 0;
}

这里采用了文件的方式生成一万个随机数

fprintf(文件指针,数据格式,数据) 可以这样理解 printf将内容打印到了屏幕上,而fprintf打印到了文件里

fscanf(文件指针,数据格式,存入地址) 可以这样理解 scanf将键盘键入的内容存到了变量,而fscanf将文件中的内容存入到了变量,若读到的为空则返回EOF

🌈本篇博客的内容【TopK,堆排序, --堆的初始化与应用】已经结束。

🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。

🌈诸君，山顶见！

【数据结构】TopK,堆排序, --堆的初始化与应用