数据结构--二叉树-堆（1）-阿里云开发者社区

树

概念

树是一种常见的非线性的数据结构，，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树的表示

对于树来说，结构比较复杂，存储起来比较困难；既要保存数据，又要保证节点与节点之间的联系；在实际中，有这几种表示方法：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。

这里介绍其中的一种：孩子兄弟表示法：

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

二叉树

概念

二叉树是一种特殊的树结构，每个节点最多可以有两个子节点。且这两个节点分别称之为左子树和右子树（左孩子和右孩子）；节点也可以没有子节点和只有一个子节点；

二叉树是有左右之分的，是一种有序树；

特殊情况：

特殊二叉树

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是，则它就是满二叉树。

完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

性质

1.若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1.

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

看下面一道例题：

堆

二叉树的顺序结构

一般的二叉树，是不适合用数组的存储结构来表示的，只有完全二叉树这种连续性的树结构才适合，在现实中，堆就是用这种结构来存储的。

注意：这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆的概念

堆其实就是一颗完全二叉树，除最后一层的叶节点，其他层的节点全是满的。堆又分为大堆和小堆。在小堆中，对于任意节点i，父节点的值小于等于子节点的值；在大堆中，对于任意节点i，父节点的值大于等于子节点的值。实际中，堆还是数组，只是存储的逻辑顺序是完全二叉树的从上到下的顺序。

堆的实现

这是堆结构

typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a; //存储的数组
  int size; //存储的大小
  int capacity; //数组的大小
}HP;

初始化

void HeapInit(HP* php)
{
  assert(php);
  php->a = NULL;
  php->capacity = php->size = 0;
}

将数组初始化为空，存储量和容量都设为0即可；

数组初始化为堆

有时我们会将一个数组变成堆的存储结构；

void HeapInitArray(HP* php, int* a, int n)
{
  assert(php);
  assert(a);
  //先将堆的数组创建空间
  php->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
  if (php->a == NULL)
  {
    perror("HeapInit Fail");
    exit(-1);
  }
  php->capacity = php->size = n;
  //复制过去
  memcpy(php->a, a,sizeof(HPDataType)* n);
  //建堆
  for (int i = 1; i < n; i++)
  {
    AdjustUp(php->a, i);//向上调整
  }
}

向上调整是孩子可能会变化为父亲，所以从第1个下标开始，而不是第0个；

向上调整

这里先说一下父亲与孩子下标的关系：

由于堆的概念，当我们插入一个数据进去或者想将数组变化为数组时，需要对这个存储的数据进行调整；而我们调整的逻辑，就是根据堆的结构去调整的。

void Swap(HPDataType* p1, HPDataType* p2)
{
  HPDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
  assert(a);
  //父亲节点
  HPDataType parent = (child - 1) / 2;
  while (child > 0)
  {
  //孩子节点的值比父亲节点的值小就交换
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (parent - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

利用循环来进行调整，这种调整，前提是前面的结构是堆，时间复杂度为O（logN）；

向下调整

有向上调整，自然有向下调整，对于堆顶的值的插入，就需要进行向下调整。

void AdjustDown(HPDataType* a, int n, int parent)
{
  assert(a);
  HPDataType 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 = child * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

这里以左孩子为主，当右孩子比左孩子大时，就将右孩子与父亲节点进行比较；

插入

我们会在数组的size的后面进行插入，也就是堆底；

void HeapPush(HP* php, HPDataType x)
{
  assert(php);
  //满扩容
  if (php->capacity == php->size)
  {
    int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
    if (tmp == NULL)
    {
      perror("Realloc fail");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newcapacity;
  }
  //插入
  php->a[php->size] = x;
  php->size++;
  //向上调整
  AdjustUp(php->a, php->size - 1);
}

删除

我们删除的是堆顶的数据，如果按常规想法，删除堆顶数据，然后进行移动，可不可行呢？

显然是不行的，解决方法是先将最后一个数据与堆顶数据交换，然后对交换后的堆顶值进行向下调整。因为调换删除后，除了堆顶，下面的数据都满足堆的条件。

void HeapPop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  //堆顶与删除数据交换
  Swap(&php->a[0], &php->a[php->size - 1]);
  
  //删除
  php->size--;
  //向下调整
  AdjustDown(php->a, php->size, 0);
  
}

打印、摧毁、判空、获取堆顶数据

//打印
void HeapPrint(HP* php)
{
  assert(php);
  for (int i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}
//摧毁
void HeapDestory(HP* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->capacity = php->size = 0;
}
HPDataType HeapTop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  return php->a[0];
}
bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}

验证

接下来就来进行验证

先验证数组初始化为堆：

int main()
{
  int a[] = { 65,100,70,32,50,60 };
  HP heap;
  HeapInitArray(&heap, a, 6);
  HeapPrint(&heap);
  return 0
}

接着依次验证插入删除和获取堆顶数据：

int main()
{
  HeapInit(&heap);
  for (int i = 0; i < 6; i++)
  {
    HeapPush(&heap, a[i]);
  }
  HeapPrint(&heap);
  HeapPop(&heap);
  HeapPrint(&heap);
  printf("%d", HeapTop(&heap));
  HeapDestory(&heap);
  return 0;
}

堆的应用

接着说堆比较常用的两个应用，堆排序和TopK问题。

堆排序

第一种方法，我们的思路是，先建立一个堆结构，然后利用堆的删除思想进行排序。

//小堆
void HeapSort(int* a, int n)
{
  //建堆
  HP hp;
  HeapInit(&hp);
  for (int i = 0; i < n; i++)
  {
    HeapPush(&hp, a[i]);
  }
  //利用堆删除原理来进行排序
  int i = 0;
  while (!HeapEmpty(&hp))
  {
    a[i++] = HeapTop(&hp);
    HeapPop(&hp);
  }
  
  HeapDestory(&hp);
}
int main()
{
  int a[] = { 2,3,5,7,4,6,8 };
  HeapSort(a, sizeof(a) / sizeof(a[0]));
  return 0;
}

这种方法，小堆对应的是升序；利用堆顶是最小的，然后对它取值后删除的原理进行排序，时间复杂度为O(N* logN * N);

还有一种方法，先对数组进行建堆，将堆顶与最后一个数据进行替换，以升序建大堆为例，最大的值与堆底替换后，那么最大的值就放在了最后的空间里了，再对数组长度做限制，那就可以完成排序了；

//小堆
void HeapSort(int* a, int n)
{
  //升序：大堆    降序：小堆
  for (int i = 1; i < n; i++)
  {
    AdjustUp(a, i);
  }
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    --end;
  }
}
int main()
{
  int a[] = { 2,3,5,7,4,6,8 };
  HeapSort(a, sizeof(a) / sizeof(a[0]));
  return 0;
}

时间复杂度O(N)=N*logN

显然下面方法排序的更快。

TopK问题

即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

void PrintTopk(const char* filename, int k)
{
  //建堆
  FILE* fout = fopen(filename, "r");
  if (fout == NULL)
  {
    perror("fout fail");
    exit(-1);
  }
  int* minheap = (int*)malloc(sizeof(int) * k);
  if (minheap == NULL)
  {
    perror("minheap fail");
    exit(-1);
  }
  //数据输入
  for (int i = 0; i < k; i++)
  {
    fscanf(fout, "%d", &minheap[i]);
  }
  //建堆
  /*for (int i = 1; i < k; i++)
  {
    AdjustUp(minheap, i);
  }*/
  for (int i = (k - 1-1) / 2; i >= 0; i--)
  {
    AdjustDown(minheap, k, i);
  }
  //交换
  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\n", minheap[i]);
  }
  fclose(fout);
}
//数据创建
void CreateNDate()
{
  int n = 1000000;
  srand(time(NULL));
  const char* file = "data.txt";
  FILE* bin = fopen(file, "w");
  if (bin == NULL)
  {
    perror("FILE Fail");
    exit(-1);
  }
  for (int i = 0; i < n; i++)
  {
    int x = (rand() + i) % 1000000;
    fprintf(bin, "%d\n", x);
  }
  fclose(bin);
}
int main()
{
  //CreateNDate();
  PrintTopk("data.txt", 5);
  return 0;
}

先利用随机数创建一个数据文件，然后先将k个数据存储进数组中，接着建堆，最后将n-k个数据与堆顶进行比较，大于堆顶就进堆；

这里有两种建堆方法，一种是向上调整的建堆，另一种是向下调整的建堆；

向上调整的建堆：

向下调整的建堆：

时间复杂度T(N)=N;

从简单的角度来看，向上调整时，堆底的最底层数据几乎是堆的一半，都需要向上调整；而向下调整，堆顶只有一个，相比之下，向下调整肯定所用时间比较少。

数据结构--二叉树-堆（1）

树

概念

相关的基本概念

树的表示

二叉树

概念

特殊二叉树

性质

堆

二叉树的顺序结构

堆的概念

堆的实现

初始化

数组初始化为堆

向上调整

向下调整

插入

删除

打印、摧毁、判空、获取堆顶数据

验证

堆的应用

堆排序

TopK问题

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构--二叉树-堆（1）

树

概念

相关的基本概念

树的表示

二叉树

概念

特殊二叉树

性质

堆

二叉树的顺序结构

堆的概念

堆的实现

初始化

数组初始化为堆

向上调整

向下调整

插入

删除

打印、摧毁、判空、获取堆顶数据

验证

堆的应用

堆排序

TopK问题

热门文章

最新文章

相关课程

相关电子书