【数据结构】堆（一）——堆的实现

news/2024/12/29 3:39:27/

作者：一个喜欢猫咪的的程序员 

专栏：《数据结构》

喜欢的话：世间因为少年的挺身而出，而更加瑰丽。                                  ——《人民日报》

目录

堆的概念及结构：

堆的实现思路：（我们以大堆为例）

需要实现的接口：

 实现的一些细节：

HeapPush函数：

Ajustup函数：

HeapPop函数：

Ajustdown函数： 

代码实现：

Heap.h文件：

Heap.c文件:

Test.c文件：

堆的概念及结构：

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

  • 父节点都比其的子节点大的完全二叉树叫做大堆。
  • 父节点都比其的子节点小的完全二叉树叫做小堆。

 堆的性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。

堆的实现思路：（我们以大堆为例）

需要实现的接口：

void Swap(HPDataType* p1, HPDataType* p2);
void HeapCreate(HP* php, HPDataType* a, int n);
void HeapPrintf(HP* php);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
int HeapSize(HP* hp);
bool HeapEmpty(HP* hp);
void Ajustdown(HPDataType* a, int n, int parent); 
void Ajustup(HPDataType* a, int n);

从堆的结构中，我们了解到堆是一个数组a，并且后续我们可能需要对数组进行扩容和缩小，因此我们还需要两个变量：有效长度size和容量capacity

 

 实现的一些细节：

 HeapInit、HeapDestroy、HeapPrintf函数没有什么好说的。

void HeapInit(HP* php)
{assert(php);php->capacity = 0;php->size = 0;php->a = NULL;
}
void HeapDestroy(HP* php)
{assert(php);assert(php->a);free(php->a);free(php);
}
void HeapPrintf(HP* php)
{assert(php);for (int i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}

HeapPush函数：

因为我们的存储结构是一个数组，Push就直接添加数据吗？

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

 以大堆为例：

100比30大，30和100需要调换位置，然后100又比70大，70和100需要再次调换位置。

我们添加的数据x作为子节点child，child可能会比它的父节点parent大。因此需要将child向上调整Ajustup。

void HeapPush(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->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size++] = x;Ajustup(php->a, php->size-1);
}

Ajustup函数：

  •  二叉树的性质：child=2*parent+1

(可参考我的另外一篇博客：http://t.csdn.cn/GLlHN)

 如果child<parent时，child和parent交换，交换后child=parent。否则break跳出循环。以此循环，当child来到根节点时结束，即：下标为0。

void Ajustup(HPDataType*a, int child)
{//N*logNassert(a);//int child = n - 1;while (child > 0){int parent = (child - 1) / 2;if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;}else{break;}}
}

 交换可以写一个函数Swap来复用，会用到很多次。

void Swap(HPDataType* p1, HPDataType* p2)
{assert(p1);assert(p2);HPDataType tmp = 0;tmp = *p1;*p1 = *p2;*p2 = tmp;
}

HeapPop函数：

出数据只能是出堆顶的元素（根节点），否则没有什么意义。

当我们将根节点删除后，它的左子节点leftchild和右子节点rightchild谁来当根节点呢？ 并且我们还得维持它是一个堆，也就是维持它是一个完全二叉树。

假设左子节点大于右子节点时，让左子节点当根节点会出现什么情况呢？

显然这种方法是不可行的！！！

 换一种思路：

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

void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size-1]);php->size--;Ajustdown(php->a, php->size-1 , 0);
}

Ajustdown函数： 

  • 由性质child=2*parent+1，反推：parent=（child-1）/2。

假设左子节点大，左子节点leftchild大于右子节点rightchild ，当左子节点小于右子节点，child++找到子节点大的那一个。

当parent>child时交换，parent=child、child=2*child+1。

void Ajustdown(HPDataType* a, int n,int parent)
{//O(N)assert(a);int child = 2 * parent+1;while (child<n){if (child + 1 < n && a[child] < a[child + 1])//  <假设左子树大{child++;}if (a[child] > a[parent])//>大堆，<为小堆{Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else{break;}}
}

HeapTop、HeapSize、HeapEmpty函数较为直接，就不做解释了。

HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}
int HeapSize(HP* php)
{assert(php);return php->size;
}
bool HeapEmpty(HP* php)
{assert(php);if (php->size == 0)return true;elsereturn false;
}

代码实现：

Heap.h文件：

#define  _CRT_SECURE_NO_WARNINGS
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
#include<time.h>
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
void Swap(HPDataType* p1, HPDataType* p2);
void HeapCreate(HP* php, HPDataType* a, int n);
void HeapPrintf(HP* php);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
int HeapSize(HP* hp);
bool HeapEmpty(HP* hp);
void Ajustdown(HPDataType* a, int n, int parent); 
void Ajustup(HPDataType* a, int n);

Heap.c文件:

#include"Heap.h"
void HeapInit(HP* php)
{assert(php);php->capacity = 0;php->size = 0;php->a = NULL;
}
void HeapDestroy(HP* php)
{assert(php);assert(php->a);free(php->a);free(php);
}
void HeapPrintf(HP* php)
{assert(php);for (int i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}
void Swap(HPDataType* p1, HPDataType* p2)
{assert(p1);assert(p2);HPDataType tmp = 0;tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void Ajustup(HPDataType*a, int child)
{//N*logNassert(a);//int child = n - 1;while (child > 0){int parent = (child - 1) / 2;if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;}else{break;}}
}
void Ajustdown(HPDataType* a, int n,int parent)
{//O(N)assert(a);int child = 2 * parent+1;while (child<n){if (child + 1 < n && a[child] < a[child + 1])//  <假设左子树大{child++;}if (a[child] > a[parent])//>大堆，<为小堆{Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else{break;}}
}
void HeapCreate(HP* php, HPDataType* a, int n)
{assert(php);HPDataType*tmp=(HPDataType*)malloc(sizeof(HPDataType) * n);if (tmp == NULL){perror("malloc fail");exit(-1);}memcpy(php->a, tmp, sizeof(HPDataType)*n);php->size = php->capacity = n;for (int i = (n - 1 - 1) / 2; i >= 0; i--){Ajustdown(php->a, n, i);}
}
void HeapPush(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->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size++] = x;Ajustup(php->a, php->size-1);
}
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size-1]);php->size--;Ajustdown(php->a, php->size-1 , 0);
}
HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}
int HeapSize(HP* php)
{assert(php);return php->size;
}
bool HeapEmpty(HP* php)
{assert(php);if (php->size == 0)return true;elsereturn false;
}

Test.c文件：

#include"Heap.h"
void test1()
{HP php;HeapInit(&php);HeapPush(&php, 75);HeapPush(&php, 56);HeapPush(&php, 30);HeapPush(&php, 25);//HeapPop(&php);int a=HeapSize(&php);printf("%d\n", a);HeapPrintf(&php);HeapPush(&php, 100);HeapPrintf(&php);HeapPop(&php);HeapPrintf(&php);HeapDestroy(&php);
}
int main()
{test1();//test2();//test3();//test4();return 0;
}


http://www.ppmy.cn/news/4399.html

相关文章

小伙伴们-GO-带你揭开Linux的神秘面纱

小伙伴们-GO-带你揭开Linux的神秘面纱

文章目录1、Linux的神秘面纱2、Linux操作系统优秀特质3、Linux操作系统应用领域4、解刨-linux系统结构5、带你一探Linux系统-满血复活的启动过程6、Linux 骨架-文件系统与目录结构6.1、Linux 文件系统概览6.2 、linux/unix 文件系统-奠基石6.2.1、 硬盘存储小知识6.2.2、 inode…
阅读更多...
SAP Gateway 后台模型的缓存设置

SAP Gateway 后台模型的缓存设置

/iwbep/cl_mgw_med_provider 类里的成员 mv_cache_active: 这个 cache 默认是开启状态。 调用 OData 服务的 MPC_EXT 类的 get_last_modified 方法获取最后一次修改的时间戳。这个时间戳(timestamp)也会影响到 cache 的行为&#xff0c;我们后续也会详细讨论。 第12 行 super 方…
阅读更多...
React Native

React Native

React NativeAndroid 基础环境配置 及 启动布局及组件内置组件第三方组件自定义组件实战应用改名Android 基础 四种组件&#xff1a; Activity服务广播接收器内容提供程序 环境配置 及 启动 查看 react native 官方文档 Node.js > 14 npm config set registry https://…
阅读更多...
Linux调试器-gdb介绍

Linux调试器-gdb介绍

文章目录gdb的基础使用gdb是什么gdb的使用gdb的下载**l 显示代码****b 行号 :打断点****info b :查看断点****d 断点序号 :删除断点****r :运行调试****n&#xff08;next&#xff09; &#xff1a;逐过程****s&#xff08;step&#xff09;&#xff1a;逐语句****c&#xff08…
阅读更多...
基于JAVA和MYSQL的图书馆座位管理系统的设计与开发

基于JAVA和MYSQL的图书馆座位管理系统的设计与开发

开发工具(eclipse/idea/vscode等)&#xff1a; 数据库(sqlite/mysql/sqlserver等)&#xff1a; 功能模块(请用文字描述&#xff0c;至少200字)&#xff1a; 11-11管理员功能模块 公告管理&#xff1a;可以对馆内开放时间、意外情况或者其他安排在网上进行发布公告&#xff0c;也…
阅读更多...
探索SpringMVC-HandlerMapping之RequestMappingHandlerMapping

探索SpringMVC-HandlerMapping之RequestMappingHandlerMapping

前言 上回我们知道HandlerMapping是用来寻找Handler的&#xff0c;并不与Handler的类型或者实现绑定&#xff0c;而是根据需要定义的。那么为什么要单独给RequestMapping实现一个HandlerMapping&#xff1f;这次咱们就来专门看看这个RequestMappingHandlerMapping。 RequestM…
阅读更多...
【HTML基础篇002】HTML之form表单超详解

【HTML基础篇002】HTML之form表单超详解

文章目录 &#x1f304;一、form表单是什么 &#x1f304;二、form表单的属性 &#x1f304;三、input中的各种Type属性值 &#x1f304;四、标签 &#x1f304;一、form表单是什么 表单是一个包含表单元素的区域。表单用于向服务器传输数据&#xff0c;从而实现用户与Web服…
阅读更多...
JVM虚拟机简介

JVM虚拟机简介

、 什么是JVM&#xff1f; JVM是Java Virtual Machine&#xff08;Java虚拟机&#xff09;的缩写&#xff0c;JVM是一种用于计算设备的规范&#xff0c;它是一个虚构出来的计算机&#xff0c;是通过在实际的计算机上仿真模拟各种计算机功能来实现的。Java虚拟机包括一套字节码指…
阅读更多...
最新文章

Copyright @ 2022~2023