AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】堆(一)

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

如果我每天都找出所犯错误和坏习惯，那么我身上最糟糕的缺点就会慢慢减少。这种自省后的睡眠将是多么惬意啊。

83d0b1f835f9475caa87db94ecd1409b_b0d728c28f9c4dee9a1e8f2a5355668c.jpeg

目录


🎄堆的概念及结构：


🎄堆的实现：


✔基本接口函数：


✔结构体：


✔HeapInit函数：


✔HeapDestory函数：


✔HeapPrint函数：


✔HeapPush函数：


✔HeapPop函数：


✔HeapTop函数：


🎄完整代码：


✔Heap.h:


✔Heap.c:


✔Text.c:

🎄堆的概念及结构：

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

堆的性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值
  • 堆总是一棵完全二叉树
  • 简单来说：
  • 父节点都比其的子节点大的完全二叉树叫做大堆。
  • 父节点都比其的子节点小的完全二叉树叫做小堆。

如图：

🎄堆的实现：

✔基本接口函数：

//堆的初始化
void HeapInit(HP* hph);
//堆的销毁
void HeapDestory(HP* hph);
//堆的打印
void HeapPrint(HP* hph);
// 堆的插入
void HeapPush(HP * hph, HPDataType x);
// 堆的删除
void HeapPop(HP* hph);
// 取堆顶的数据
HPDataType HeapTop(HP* hph);
// 堆的数据个数
int HeapSize(HP* hph);
// 堆的判空
int HeapEmpty(HP* hph);

✔结构体：

typedef int HPDataType;
typedef struct heap
{
  HPDataType* a;
  int capacity;
  int size;
}HP;

✔HeapInit函数： 

//堆的初始化
void HeapInit(HP* hph)
{
  assert(hph);
  hph->a = NULL;
  hph->capacity = hph->size = 0;
}


✔HeapDestory函数：

//堆的销毁
void HeapDestory(HP* hph)
{
  assert(hph);
  free(hph->a);
  hph->a = NULL;
  hph->capacity = 0;
  hph->size = 0;
}


✔HeapPrint函数： 

//堆的打印
void HeapPrint(HP* hph)
{
  for (int i = 0; i < hph->size; ++i)
  {
    printf("%d ", hph->a[i]);
  }
  printf("\n");
}


✔HeapPush函数：

当capacity==size时扩容（包括初始化的方案），当size==0时，扩容4个空间，否则扩容二倍的空间，capacity也跟着扩大，当push后size++。

cfe90b09be30827842027fe8fdadb437_a73f2d55707c4d19b709da8fb4516461.png

Swap交换函数：

void Swap(HPDataType* p1, HPDataType* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
//向上调整
//child和parent都是下标
void AdjusUp(HPDataType* a, int child)
{
  int parent = (child - 1) / 2;
  while (child>0)
  {
    if (a[parent] < a[child])
    {
      Swap(&a[parent], &a[child]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
// 堆的插入
void HeapPush(HP* hph, HPDataType x)
{
  assert(hph);
  //扩容
  if (hph->capacity == hph->size)
  {
    int newcapacity = hph->capacity == 0 ? 4 : hph->capacity * 2;
    HPDataType* tmp = (HPDataType* )realloc(hph->a, sizeof(HPDataType) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail:");
      exit(-1);
    }
    hph->a = tmp;
    hph->capacity = newcapacity;
  }
  hph->a[hph->size] = x;
  hph->size++;
  //向上调整
  AdjusUp(hph->a, hph->size - 1);
}

✔HeapPop函数：

出堆顶的元素，让第一个位置的值和最后一个位置的值交换，再size--就相当于删除了，但交换上去的值在根节点的位置上，我们无法维持是大堆的情况，因此还需要向下调整Ajustdown。

c269c6a2ca527b278c29532a4bdbf5ae_022bf8df0dc5467ebba5897215082fc2.png

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    if (child + 1< n && a[child] < a[child + 1])
    {
      child = child + 1;
    }
    //child 大于 parent 就交换
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
// 堆的删除
void HeapPop(HP* hph)
{
  assert(hph);
  assert(!HeapEmpty(hph));
  Swap(&hph->a[0], &hph->a[hph->size - 1]);
  hph->size--;
  AdjustDown(hph->a, hph->size, 0);
}

✔HeapTop函数：

// 取堆顶的数据
HPDataType HeapTop(HP* hph)
{
  assert(hph);
  assert(hph->size > 0);
  return hph->a[0];
}

🎄完整代码：

✔Heap.h:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int HPDataType;
typedef struct heap
{
  HPDataType* a;
  int capacity;
  int size;
}HP;
//堆的初始化
void HeapInit(HP* hph);
//堆的销毁
void HeapDestory(HP* hph);
//堆的打印
void HeapPrint(HP* hph);
// 堆的插入
void HeapPush(HP * hph, HPDataType x);
// 堆的删除
void HeapPop(HP* hph);
// 取堆顶的数据
HPDataType HeapTop(HP* hph);
// 堆的数据个数
int HeapSize(HP* hph);
// 堆的判空
int HeapEmpty(HP* hph);

✔Heap.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include "heap.h"
//堆的打印
void HeapPrint(HP* hph)
{
  for (int i = 0; i < hph->size; ++i)
  {
    printf("%d ", hph->a[i]);
  }
  printf("\n");
}
//堆的初始化
void HeapInit(HP* hph)
{
  assert(hph);
  hph->a = NULL;
  hph->capacity = hph->size = 0;
}
//堆的销毁
void HeapDestory(HP* hph)
{
  assert(hph);
  free(hph->a);
  hph->a = NULL;
  hph->capacity = 0;
  hph->size = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
//向下调整
//child和parent都是下标
void AdjusUp(HPDataType* a, int child)
{
  int parent = (child - 1) / 2;
  while (child>0)
  {
    if (a[parent] < a[child])
    {
      Swap(&a[parent], &a[child]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
// 堆的插入
void HeapPush(HP* hph, HPDataType x)
{
  assert(hph);
  //扩容
  if (hph->capacity == hph->size)
  {
    int newcapacity = hph->capacity == 0 ? 4 : hph->capacity * 2;
    HPDataType* tmp = (HPDataType* )realloc(hph->a, sizeof(HPDataType) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail:");
      exit(-1);
    }
    hph->a = tmp;
    hph->capacity = newcapacity;
  }
  hph->a[hph->size] = x;
  hph->size++;
  //向下调整
  AdjusUp(hph->a, hph->size - 1);
}
//向上调整
void AdjustDown(HPDataType* a, int n, int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    if (child + 1< n && a[child] < a[child + 1])
    {
      child = child + 1;
    }
    //child 大于 parent 就交换
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
// 堆的删除
void HeapPop(HP* hph)
{
  assert(hph);
  assert(!HeapEmpty(hph));
  Swap(&hph->a[0], &hph->a[hph->size - 1]);
  hph->size--;
  AdjustDown(hph->a, hph->size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(HP* hph)
{
  assert(hph);
  assert(hph->size > 0);
  return hph->a[0];
}
// 堆的数据个数
int HeapSize(HP* hph)
{
  assert(hph);
  return hph->size;
}
// 堆的判空
int HeapEmpty(HP* hph)
{
  assert(hph);
  return hph->size == 0;
}

✔Text.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include "heap.h"
void Heap()
{
  int arry[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
  HP hph;
  HeapInit(&hph);
  HeapPrint(&hph);
  for (int i = 0; i < sizeof(arry) / sizeof(int); i++)
  {
    HeapPush(&hph, arry[i]);
  }
  HeapPrint(&hph);
  HeapPush(&hph, 100);
  HeapPrint(&hph);
  HeapPop(&hph);
  HeapPrint(&hph);
  HeapDestory(&hph);
}
void TestHeap2()
{
  int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
  HP hp;
  HeapInit(&hp);
  for (int i = 0; i < sizeof(array) / sizeof(int); ++i)
  {
    HeapPush(&hp, array[i]);
  }
  while (!HeapEmpty(&hp))
  {
    printf("%d ", HeapTop(&hp));
    HeapPop(&hp);
  }
  HeapDestroy(&hp);
}
int main()
{
  TestHeap2();
  return 0;
}
文章标签：
存储
关键词：
数据结构堆
日出等日落
目录
相关文章
ephemerals__
|
11月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
425 16
2的n次方_
|
存储 Java
【数据结构】优先级队列（堆）从实现到应用详解
本文介绍了优先级队列的概念及其底层数据结构——堆。优先级队列根据元素的优先级而非插入顺序进行出队操作。JDK1.8中的`PriorityQueue`使用堆实现，堆分为大根堆和小根堆。大根堆中每个节点的值都不小于其子节点的值，小根堆则相反。文章详细讲解了如何通过数组模拟实现堆，并提供了创建、插入、删除以及获取堆顶元素的具体步骤。此外，还介绍了堆排序及解决Top K问题的应用，并展示了Java中`PriorityQueue`的基本用法和注意事项。
2的n次方_
263 5
【数据结构】优先级队列（堆）从实现到应用详解
神明木佑
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
神明木佑
351 1
椰椰椰耶
【数据结构】大根堆和小根堆
【数据结构】大根堆和小根堆
椰椰椰耶
441 0
平凡程序猿~
|
存储 算法 搜索推荐
数据结构--堆的深度解析
数据结构--堆的深度解析
平凡程序猿~
552 1
平凡程序猿~
|
存储 算法 调度
数据结构--二叉树的顺序实现（堆实现）
数据结构--二叉树的顺序实现（堆实现）
平凡程序猿~
210 1
是店小二呀
|
存储 算法 分布式数据库
【初阶数据结构】理解堆的特性与应用：深入探索完全二叉树的独特魅力
【初阶数据结构】理解堆的特性与应用：深入探索完全二叉树的独特魅力
是店小二呀
223 1
阿客不是客
|
存储 算法
探索数据结构：分支的世界之二叉树与堆
探索数据结构：分支的世界之二叉树与堆
阿客不是客
141 0
GuGuStudy
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
GuGuStudy
164 0
努力学习的小廉
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现
努力学习的小廉
115 0

热门文章

最新文章

  • 1
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
  • 2
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
  • 3
    软考中级软件设计师专项-数据结构与算法上篇
  • 4
    【Redis】常用数据结构之List篇：从常用命令到典型使用场景
  • 5
    Redis数据结构：别小看这5把“瑞士军刀”，用好了性能飙升！
  • 6
    Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
  • 7
    【Redis】 常用数据结构之String篇：从SET/GET到INCR的超全教程
  • 8
    Redis基础命令与数据结构概览
  • 9
    GPS北斗双模技术应用开发研究—数据结构扩展
  • 10
    堆和栈的区别 【转】
  • 1
    重拾数据结构和算法——脑图
    156
  • 2
    栈的最后表演：逆波兰表达式求值
    86
  • 3
    栈与队列
    58
  • 4
    深入浅出 栈和队列（附加循环队列、双端队列）
    204
  • 5
    【数据结构】----链表--双向链表
    89
  • 6
    【数据结构】线性表----链表详解
    226
  • 7
    【数据结构】----顺序表项目-通讯录
    76
  • 8
    【数据结构】线性表----顺序表详解
    184
  • 9
    题目----数据结构线性表----字符串逆序
    83
  • 10
    深入理解Python的数据结构：列表与元组
    214

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    开箱即用-OSS无代理备份