数据结构初阶 堆(二)

简介: 数据结构初阶 堆(二)

一. 堆的接口函数(续)

虽然我们的上一篇博客已经写过了堆的前面一些接口函数

这里我们再重复一遍

1. 结构体形式

我们这里形式上使用一个数组来表示一个逻辑上的二叉树

typedef int HPDateType;
 
typedef struct Heap
{
  HPDateType* a;
  int size;
  int capacity;
}HP;

2. 初始化和销毁

这里的两个接口函数都很简单 我们直接连起来动手实现一下

初始化

void HeapInit(HP* php)
{
  assert(php);
  php->a = (HPDateType*)malloc(sizeof(HPDateType) * 4);
  if (php->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  php->size =0;
  php->capacity = 4;
}

销毁

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

3. 添加数据(小堆为例)

当我们这里插入一个10的时候 这里明显是错误的啊 怎么办呢?

这个时候我们就需要将它跟它的父亲比较 是否小于它的父亲

如果不小于就填入

如果大于就交换它和它的父亲

知道孩子等于0为止

下面开始写代码

void HeapPush(HP* php, HPDateType x)
{
  assert(php);
  if (php->size == php->capacity)
  {
    HPDateType* tmp = (HPDateType*)realloc(php->a,sizeof(HPDateType) * php->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    php->a = tmp;
    php->capacity *= 2;
  }
  php->a[php->size] = x;
  php->size++;
  AdJustUp(php->a, php->size - 1);
}

这里因为判断是否需要调整这个函数要使用很多次

所以说我们单独写出一个函数出来

void Swap(HPDateType* p1, HPDateType* p2)
{
  HPDateType x = *p1;
  *p1 = *p2;
  *p2 = x;
}
//除child这个位置,前面数据构成堆
//向上调整
void AdJustUp(HPDateType* 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;
    }
  }
}

整体代码如下

1. vovoid Swap(HPDateType* p1, HPDateType* p2)
{
  HPDateType x = *p1;
  *p1 = *p2;
  *p2 = x;
}
//除child这个位置,前面数据构成堆
//向上调整
void AdJustUp(HPDateType* 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, HPDateType x)
{
  assert(php);
  if (php->size == php->capacity)
  {
    HPDateType* tmp = (HPDateType*)realloc(php->a,sizeof(HPDateType) * php->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    php->a = tmp;
    php->capacity *= 2;
  }
  php->a[php->size] = x;
  php->size++;
  AdJustUp(php->a, php->size - 1);
}

4. 删除数据

 

我们想要删除堆中的一个数据 还要不改变这个堆的结构 这个时候怎么办呢

这个时候我们这里给出一种很巧妙的解法

我们先将最前面的元素和最后面的元素交换位置

然后再删除掉堆最后面的元素

之后开始向下调整这个堆

如上图所示

下面是删除数据的大体逻辑

void HeapPop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(&php));
  //删除数据
  Swap(&php->a[0], &php->a[php->size - 1]);
  php->size--;

这里我们还需要再写一个函数向下调整

void AdJustDown(HPDateType* 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[child], &a[parent]);
      parent = child;
      //更新孩子的位置
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

调整函数如上

我们再来整体看看这个函数

void AdJustDown(HPDateType* 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[child], &a[parent]);
      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);
}

测试一下试试


5. 返回大小

这个很简单 返回size大小

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

7. 判断为空

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

8.返回堆顶数据

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


以上便是本文所有内容了,如有错误请各位大佬不吝赐教,感谢留言

目录
相关文章
|
2天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
32 16
|
23天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
61 1
|
2月前
|
存储 Java
【数据结构】优先级队列(堆)从实现到应用详解
本文介绍了优先级队列的概念及其底层数据结构——堆。优先级队列根据元素的优先级而非插入顺序进行出队操作。JDK1.8中的`PriorityQueue`使用堆实现,堆分为大根堆和小根堆。大根堆中每个节点的值都不小于其子节点的值,小根堆则相反。文章详细讲解了如何通过数组模拟实现堆,并提供了创建、插入、删除以及获取堆顶元素的具体步骤。此外,还介绍了堆排序及解决Top K问题的应用,并展示了Java中`PriorityQueue`的基本用法和注意事项。
47 5
【数据结构】优先级队列(堆)从实现到应用详解
|
1月前
|
存储 算法 调度
数据结构--二叉树的顺序实现(堆实现)
数据结构--二叉树的顺序实现(堆实现)
|
1月前
|
存储 算法 分布式数据库
【初阶数据结构】理解堆的特性与应用:深入探索完全二叉树的独特魅力
【初阶数据结构】理解堆的特性与应用:深入探索完全二叉树的独特魅力
|
24天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
26天前
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
29 0
|
29天前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现
|
30天前
【数据结构】大根堆和小根堆
【数据结构】大根堆和小根堆
20 0
|
1月前
|
存储 算法 搜索推荐
数据结构--堆的深度解析
数据结构--堆的深度解析