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

简介: 注意传过去的参数是插入的位置,即插入前的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 的结点有:
  1. 若 i>0 , i 位置结点的双亲序号: (i-1)/2 ; i=0 , i 为根结点编号,⽆双亲结点
  2. 若 2i+1<n,左孩⼦序号: 2i+1 , 2i+1>=n 则⽆左孩⼦
  3. 若 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];
}

相关文章
|
20天前
|
存储 Java
【数据结构】优先级队列(堆)从实现到应用详解
本文介绍了优先级队列的概念及其底层数据结构——堆。优先级队列根据元素的优先级而非插入顺序进行出队操作。JDK1.8中的`PriorityQueue`使用堆实现,堆分为大根堆和小根堆。大根堆中每个节点的值都不小于其子节点的值,小根堆则相反。文章详细讲解了如何通过数组模拟实现堆,并提供了创建、插入、删除以及获取堆顶元素的具体步骤。此外,还介绍了堆排序及解决Top K问题的应用,并展示了Java中`PriorityQueue`的基本用法和注意事项。
23 5
【数据结构】优先级队列(堆)从实现到应用详解
|
1月前
|
存储 机器学习/深度学习
【数据结构】二叉树全攻略,从实现到应用详解
本文介绍了树形结构及其重要类型——二叉树。树由若干节点组成,具有层次关系。二叉树每个节点最多有两个子树,分为左子树和右子树。文中详细描述了二叉树的不同类型,如完全二叉树、满二叉树、平衡二叉树及搜索二叉树,并阐述了二叉树的基本性质与存储方式。此外,还介绍了二叉树的实现方法,包括节点定义、遍历方式(前序、中序、后序、层序遍历),并提供了多个示例代码,帮助理解二叉树的基本操作。
45 13
【数据结构】二叉树全攻略,从实现到应用详解
|
28天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
28天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构,其中节点的度为其分支数量,树的度为树中最大节点度数。二叉树是一种特殊的树,其节点最多有两个子节点,具有多种性质,如叶子节点数与度为2的节点数之间的关系。此外,还介绍了二叉树的不同形态,包括满二叉树、完全二叉树、二叉排序树和平衡二叉树,并探讨了二叉树的顺序存储和链式存储结构。
|
28天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
1月前
|
存储 程序员 C语言
堆和栈之间有什么区别
【9月更文挑战第1天】堆和栈之间有什么区别
126 0
|
2月前
|
算法 机器人
【数据结构】什么是堆
【数据结构】什么是堆
36 0
|
2月前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称,即左右子树是否对称.
|
7天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈