【数据结构】--- 博主拍了拍你并向你扔了一“堆”二叉树(堆的概念+结构+代码实现)

2023-06-28 89

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构学习第十三弹——二叉树——堆的概念+结构+代码实现

🌟一、二叉树的顺序结构及实现：

🌟二、堆的概念及结构：

如果有一个关键码的集合K = { ，，，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质:

完全二叉树

大堆:树任何一个父亲都大于或等于孩子

小堆:树任何一个父亲都小于或等于孩子

🌟三、堆的代码实现：

对于堆的代码实现无非就是先定义结构，包括初始化插入删除堆顶元素堆顶数据堆数据个数判空释放

🌏3.1 堆的创建：

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

🌏3.2 堆的结构：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

🌏3.4 堆的插入：

💫3.4.1 堆向上调整算法：

向堆中插入数据，需要使用向上调整算法调整，因为向堆中插入数据是将数据插入到下标为size的位置，此时就不满足小堆 (大堆)，因此，需要堆其进行调整，向上调整算法和向下调整算法思路类似，此处以小堆为例，向上调整法只需从插入的节点位置开始和父节点比较。

📝3.4.1.1 代码(以小堆为例)：

void AdjustUp(HPDataType* a, int child)
{
  int parent = (child - 1) / 2;
  while (child>0)
  {
    if (a[child] < a[parent])
    {
      HPDataType tmp = a[child];
      a[child] = a[parent];
      a[parent] = tmp;
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

📝3.4.1.2 流程图：

💫3.4.2 堆向上调整算法(插入)：

void HeapPush(HP* php, HPDataType x)
{
  assert(php);
  if (php->size == php->capacity)
  {
    int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newCapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    php->a = tmp;
    php->capacity = newCapacity;
  }
  php->a[php->size] = x;
  AdjustUp(php->a, php->size);//堆向上调整算法
  php->size++;
}

🌏3.5 堆的删除(删除堆顶元素)：

对于堆顶元素的删除，可能想到了覆盖，但是覆盖显然是不太满足的因为当我们删除堆顶元素本来关系为兄弟的节点就变成了父子等导致关系错乱(一旦关系错乱就导致不满足大堆/小堆中双亲与子孙的关系—小堆为例双亲小于孩子)

如图：

所以我们另辟蹊径：先交换堆顶数据和最后一个数据这样中间的关系并没有造成混乱，然后数据个数减减，之后调整最后一个数据交换上去后的堆(只需要比较这个堆顶元素和孩子的关系达到满足关系) — 先比较它的两个孩子(左孩子和右孩子)大小关系，找到小的一方再和堆顶数据比较若小其则交换依次往后比较交换直到孩子的下标>=数据个数就停止。

注意一点：可能它只有左孩子没有右孩子，所以我们要对右孩子判断一下右孩子下标要小于堆数据个数才行不然就越界了

💫3.5.1 堆向下调整算法：

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

📝3.5.1.1 代码(以小堆为例)：

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+1<n判断右孩子下标满足不越界再比较
    //a[child + 1] < a[child]右孩子<左孩子,就代表右孩子小child++就是右孩子
    {
      child++;
    }
    if (a[child] < a[parent])
    {
      Swap(&a[parent], &a[child]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

📝3.5.1.2 流程图：

💫3.5.2 堆向下调整算法(删除)：

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);
}

🌏3.6 堆的堆顶数据：

HPDataType HeapTop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  return php->a[0];
}

🌏3.7 堆的堆数据个数：

int HeapSize(HP* php)
{
  assert(php);
  return php->size;
}

🌏3.8 判空：

bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}

🌏3.9 释放：

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

🌟四、堆实现的完整代码：

//Heap.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
//Heap.c
#include"Heap.h"
void HeapInit(HP* php)
{
  assert(php);
  php->a = NULL;
  php->size = 0;
  php->capacity = 0;
}
void HeapDestroy(HP* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->capacity = php->size = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
  HPDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void AdjustUp(HPDataType* 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 HeapPush(HP* php, HPDataType x)
{
  assert(php);
  if (php->size == php->capacity)
  {
    int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newCapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    php->a = tmp;
    php->capacity = newCapacity;
  }
  php->a[php->size] = x;
  AdjustUp(php->a, php->size);
  php->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[parent], &a[child]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
//删除堆顶数据
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);
}
HPDataType HeapTop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  return php->a[0];
}
bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}
int HeapSize(HP* php)
{
  assert(php);
  return php->size;
}
//Test.c
#include"Heap.h"
void HPTest()
{
  HP hp;
  HeapInit(&hp);
  int a[] = { 65,100,70,32,50,60 };
  for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
  {
    HeapPush(&hp, a[i]);
  }
  while (!HeapEmpty(&hp))
  {
    int top = HeapTop(&hp);
    printf("%d\n", top);
    HeapPop(&hp);
  }
}
int main()
{
  HPTest();
  return 0;
}

🌟五、堆伏笔：

对于上述代码实现后，运行会发现以小堆为例我们完成的堆是一个有序的顺序，这就为下一章对于堆的应用做了一个铺垫

😽总结

😽Ending,今天的二叉树 — 堆的概念+结构+代码实现的内容就到此结束啦~，如果后续想了解更多，就请关注我吧。