【初阶数据结构篇】实现顺序结构二叉树（堆的实现方法）-阿里云开发者社区

【初阶数据结构篇】实现顺序结构二叉树（堆的实现方法）

2024-08-19 20

版权

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

简介： 注意传过去的参数是插入的位置，即插入前的size，在调整完后再将size++

实现顺序结构二叉树（堆）

前言

⼀般堆使⽤顺序结构的数组来存储数据，堆是⼀种特殊的⼆叉树，具有⼆叉树的特性的同时，还具备其他的特性

代码位置

[gitee](Heap/Heap · petrichor/2024-summer-c-language - 码云 - 开源中国 (gitee.com))

堆的概念与结构

概念

如果有⼀个关键码的集合 K = {k0 , k1 , k2, …，kn−1 }，把它的所有元素按完全⼆叉树的顺序存储⽅式存储，在⼀个⼀维数组中，并满⾜： Ki<=K2i+1 且 Ki<=K2i+2（Ki >= K2i+1 且Ki >=K2i+2）（ i = 0、1、2…），则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆叫做最⼩堆或⼩根堆。

堆具有以下性质

堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；
堆总是⼀棵完全⼆叉树。

完全二叉树性质

对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：

若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点
若 2i+1<n，左孩⼦序号： 2i+1 ， 2i+1>=n 则⽆左孩⼦
若 2i+2<n，右孩⼦序号： 2i+2 ， 2i+2>=n 否则⽆右孩⼦

堆的实现

堆的底层结构为数组

本篇建小堆！！！大堆同理

Heap.h(其中方法会一一讲到)

定义堆结构
将存储数据类型重命名(方便之后替换->例如我们要求堆内存储char类型数据，只用改一行代码即可)
所写的函数的声明，声明的时候参数只需要类型就可以了，名字加不加都一样

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义堆的结构---数组

typedef int HPDataType;

typedef struct Heap
{
  HPDataType* arr;
  int size;//有效的数据个数
  int capacity;//空间大小
}HP;

void HPInit(HP* php);
void HPDestroy(HP* php);

void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);

HPDataType HPTop(HP* php);
// 判空
bool HPEmpty(HP* php);

test.c

用来测试我们写的函数(函数的调用)
这一部分就是自己写的时候用的测试用例，随便什么都行

最好是写一个方法测试一次，不然找错误的时候会很痛苦😜

#include"Heap.h"

void test01()
{
  HP hp;
  HPInit(&hp);
  
  int arr[] = { 17,20,10,13,19,15 };
  for (int i = 0; i < 6; i++)
  {
    HPPush(&hp, arr[i]);
  }

  //HPPop(&hp);

  while (!HPEmpty(&hp))
  {
    printf("%d ", HPTop(&hp));
    HPPop(&hp);
  }


  HPDestroy(&hp);
}

int main()
{
  test01();
  return 0;
}

Heap.c

函数方法的实现，重点重点！！！

养成习惯，用assert宏来判断指针是否为空（避免使用时传入空指针，后续解引用都会报错）

堆初始化和销毁

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

void HPDestroy(HP* php)
{
  assert(php);
  if (php->arr)
    free(php->arr);

  php->arr = NULL;
  php->size = php->capacity = 0;
}

堆的插入

void HPPush(HP* php, HPDataType x)
{
  assert(php);
  //判断空间是否足够
  if (php->size == php->capacity)
  {
    //扩容
    int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
    HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
    if (tmp == NULL)
    {
      perror("realloc fail!");
      exit(1);
    }
    php->arr = tmp;
    php->capacity = newCapacity;
  }
  php->arr[php->size] = x;
  
  AdjustUp(php->arr, php->size);

  ++php->size;
}

第一步，和顺序的插入一样，判断空间是否足够然后插入
第二步，根据堆的特性实行向上调整算法
注意传过去的参数是插入的位置，即插入前的size，在调整完后再将size++

向上调整算法

void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

void AdjustUp(HPDataType* arr,int child)
{
  int parent = (child - 1) / 2;
  while (child > 0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换
  {
    if (arr[child] < arr[parent])
    {
      Swap(&arr[parent], &arr[child]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  } 
}

两个参数

调整的堆
孩子节点：即进行加一前的size

利用父节点和孩子结点的关系

堆的判空

和顺序表相同

// 判空
bool HPEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}

堆的删除数据

出堆：出的是栈顶的元素！！！

void HPPop(HP* php)
{
  assert(php && php->size);

  //arr[0]  arr[size-1]
  Swap(&php->arr[0], &php->arr[php->size - 1]);
  --php->size;
  AdjustDown(php->arr, 0, php->size);
}

判断是否为空
将堆顶数据与最后一个数据交换
此时先将size–，因为向下调整是在数据有效数据个数中调整！

向下调整算法

void AdjustDown(HPDataType* arr, int parent, int n)
{
  int child = parent * 2 + 1;//左孩子
  //while (parent < n)
  while (child < n)
  {
    //找左右孩子中找最小的
    if (child + 1 < n && arr[child] > arr[child + 1])
    {
      child++;
    }
    if (arr[child] < arr[parent])
    {
      Swap(&arr[child], &arr[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

三个参数

需要调整的堆(数组)
父节点，因为出堆都是交换最后一个到栈顶，所以此处就是0
数组有效数据个数，即size–

循环结束条件：child<n（每次循环完后child都是parent*2+1，只要child不越界即可）
在找左右孩子最小时，先要判断有没有右孩子

取堆顶数据

也很简单，没什么好说的啦

HPDataType HPTop(HP* php)
{
  assert(php && php->size);
  return php->arr[0];
}

Heap.c（完整版）

#include"Heap.h"
void HPInit(HP* php)
{
  assert(php);
  php->arr = NULL;
  php->size = php->capacity = 0;
}
void HPDestroy(HP* php)
{
  assert(php);
  if (php->arr)
    free(php->arr);
  php->arr = NULL;
  php->size = php->capacity = 0;
}

void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

void AdjustUp(HPDataType* arr,int child)
{
  int parent = (child - 1) / 2;

  while (child > 0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换
  {
    if (arr[child] < arr[parent])
    {
      Swap(&arr[parent], &arr[child]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
  
}

void HPPush(HP* php, HPDataType x)
{
  assert(php);
  //判断空间是否足够
  if (php->size == php->capacity)
  {
    //扩容
    int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
    HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
    if (tmp == NULL)
    {
      perror("realloc fail!");
      exit(1);
    }
    php->arr = tmp;
    php->capacity = newCapacity;
  }
  php->arr[php->size] = x;
  
  AdjustUp(php->arr, php->size);

  ++php->size;
}

void AdjustDown(HPDataType* arr, int parent, int n)
{
  int child = parent * 2 + 1;//左孩子
  //while (parent < n)
  while (child < n)
  {
    //找左右孩子中找最小的
    if (child + 1 < n && arr[child] > arr[child + 1])
    {
      child++;
    }
    if (arr[child] < arr[parent])
    {
      Swap(&arr[child], &arr[parent]);
      parent = child;
      child = parent * 2 + 1;

    }
    else
    {
      break;
    }
  }
}

void HPPop(HP* php)
{
  assert(php && php->size);

  //arr[0]  arr[size-1]
  Swap(&php->arr[0], &php->arr[php->size - 1]);

  --php->size;

  AdjustDown(php->arr, 0, php->size);
}
// 判空
bool HPEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}
//取堆顶数据
HPDataType HPTop(HP* php)
{
  assert(php && php->size);
  return php->arr[0];
}