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

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

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


🌟二、堆的概念及结构:


如果有一个关键码的集合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,今天的二叉树 — 堆的概念+结构+代码实现 的内容就到此结束啦~,如果后续想了解更多,就请关注我吧。

相关文章
|
1天前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
1天前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(三)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
1天前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(二)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
1天前
|
存储
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(一)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
1天前
【高阶数据结构】深度探索二叉树进阶:二叉搜索树概念及其高效实现(三)
【高阶数据结构】深度探索二叉树进阶:二叉搜索树概念及其高效实现
|
1天前
|
存储
【高阶数据结构】深度探索二叉树进阶:二叉搜索树概念及其高效实现(二)
【高阶数据结构】深度探索二叉树进阶:二叉搜索树概念及其高效实现
|
1天前
【高阶数据结构】深度探索二叉树进阶:二叉搜索树概念及其高效实现(一)
【高阶数据结构】深度探索二叉树进阶:二叉搜索树概念及其高效实现
|
1天前
|
存储
【初阶数据结构】树与二叉树:从零开始的奇幻之旅
【初阶数据结构】树与二叉树:从零开始的奇幻之旅
|
1月前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
1月前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。