堆的实现思路

什么是堆?堆是一种 基于树结构的数据结构,它是一棵二叉树 ,具有以下两个特点:堆是一个完全二叉树,即除了最后一层,其他层都是满的,最后一层从左到右填满。堆中每个节点都满足堆的特性,即父节点的值要么等于或者大于(小于)子节点的值。1.1 堆的分类堆一般分为两类: 大堆和小堆 。
大堆中,父节点的值大于或等于子节点的值,小堆中,父节点的值小于或等于子节点的值。堆的主要应用是在排序和优先队列中。
以下分别为两个堆(左大堆,右小堆):
part2 堆的实现思路2.1 使用什么实现?
逻辑结构如上, 然而这仅仅是我们想像出来的而已,而实际上的堆的物理结构是一个完全二叉树 , 通常是 用数组实现的 。如下:
对此,这就要引申出一个问题?我们该如何分辨父节点以及子节点呢?如下:
2.2 怎么分辨父节点以及子节点?通常我们的数组下标为“0”处即为根节点,也就是说我们一定知道一个父节点!并且我们也有“计算公式”来计算父节点以及子节点。(先记住,后面实现有用!!!)也就是说我们也可以通过公式从每一个位置计算父节点以及子节点!如下:
2.3 总体实现思路先建立一个结构体,由于堆的结构实际上是一颗完全二叉树,因此我们的 结构跟二叉树一样即可! 接着,想想我们的堆需要实现的功能? 构建、销毁、插入、删除、取堆顶的数据、取数据个数、判空 。(⊙o⊙)…基本的就这些吧哈~
接着按照 定义函数接口->实现各个函数功能->测试测试->收工(-_^) o(  ̄▽ ̄ )ブ
part3** 堆的实现**3.1 结构体以及接口的实现typedefint hpdatatype;typedefstruct heap{ hpdatatype* _a; int _size; int _capacity;}heap;// 堆的构建void heapcreate(heap* hp, hpdatatype* a, int n);// 堆的销毁void heapdestory(heap* hp);// 堆的插入void heappush(heap* hp, hpdatatype x);// 堆的删除void heappop(heap* hp);// 取堆顶的数据hpdatatype heaptop(heap* hp);// 堆的数据个数int heapsize(heap* hp);// 堆的判空int heapempty(heap* hp);3.2 堆的两种建堆方式在实现以上的接口之前,我们必须要知道堆的两种建堆方式!!!
并且仅仅通过调整建堆方式的符号,我们就可以轻易控制大小堆,具体看代码注释!
建堆有两种方式,分别是 自底向上建堆以及自顶向下建堆。 具体简介如下:
自底向上建堆:自底向上建堆是指按照原始数组顺序依次插入元素,然后对每个插入的元素执行向上调整的操作,使得堆的性质保持不变。这种方法需要对每个元素都进行调整操作,时间复杂度为 o(nlogn)。自顶向下建堆:自顶向下建堆是指从堆顶开始,对每个节点执行向下调整操作,使得堆的性质保持不变。这种方法需要从根节点开始递归向下调整,时间复杂度为 o(n)。因此,自顶向下建堆的效率比自底向上建堆要高。以上两种建堆方式,实际上是基于两种调整方法,接下来将详细介绍:
向上调整方法堆的向上调整方法将新插入的节点从下往上逐层比较,如果当前节点比其父节点大(或小,根据是大根堆还是小根堆),则交换这两个节点。一直向上比较,直到不需要交换为止。这样可以保证堆的性质不变。
具体步骤如下:
将新插入的节点插入到堆的最后一位。获取该节点的父节点的位置,比较该节点与其父节点的大小关系。如果该节点比其父节点大(或小,根据是大根堆还是小根堆),则交换这两个节点。重复步骤2-3,直到不需要交换为止,堆的向上调整完成。堆的向上调整的时间复杂度为o(logn),其中n为堆的大小。一图让你了解~:
实现如下:
void swap(hpdatatype* s1, hpdatatype* s2){ hpdatatype temp = *s1; *s1 = *s2; *s2 = temp;}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; } }}向下调整方法堆的向下调整方法是指将某个节点的值下放至其子节点中,以维护堆的性质的过程。
假设当前节点为 i,其左子节点为 2i+1,右子节点为 2i+2,堆的大小为 n
则向下调整的步骤如下:
从当前节点 i 开始,将其与其左右子节点中较小或较大的节点比较,找出其中最小或最大的节点 j。如果节点 i 小于等于(或大于等于,取决于是最小堆还是最大堆)节点 j,则说明它已经满足堆的性质,调整结束;否则,将节点 i 与节点 j 交换位置,并将当前节点 i 更新为 j。重复执行步骤 1 和步骤 2,直到节点 i 没有子节点或已经满足堆的性质。一图让你了解~:
实现如下:
void swap(hpdatatype* s1, hpdatatype* s2){ hpdatatype temp = *s1; *s1 = *s2; *s2 = temp;}void adjustdown(hpdatatype* a, int n, int parent)//向下调整{ int child = parent * 2 + 1; while (child < n) { if (child + 1 a[child])//找出两个孩子中较大的那个,此为大堆,如果要实现小堆则 改 > { ++child; } if (a[child] > a[parent])//此为大堆,如果要实现小堆则 改 > { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } }}3.3 堆的构建void heapcreate(heap* hp, hpdatatype* a, int n){ assert(hp); assert(a); hp- >_a = (hpdatatype*)malloc(sizeof(hpdatatype) * n); if (!hp- >_a) { perror(malloc fail); exit(-1); } hp- >_capacity = hp- >_size = n; //将a中的元素全部转移到堆中 memcpy(hp- >_a, a, sizeof(hpdatatype) * n); //建堆 for (int i = 1; i _a, i);//按向上调整,此建立大堆 }}本文的构建方法是 通过传递一个数组以及传递一个数组大小来构建的 ,里面包括了堆结构体的初始化操作,基本的建堆方式则是通过向上调整方法建堆。
3.4 堆的销毁void heapdestory(heap* hp){ assert(hp); free(hp- >_a); hp- >_a = null; hp- >_capacity = hp- >_size = 0;}就正常的销毁操作?大家应该都懂(确信) (o°ω°o)
3.5 堆的插入void heappush(heap* hp, hpdatatype x){ assert(hp); if (hp- >_capacity == hp- >_size)//扩容 { int newcapacity = hp- >_capacity == 0 ? 4 : hp- >_capacity * 2; hpdatatype* new = (hpdatatype*)realloc(hp- >_a, sizeof(hpdatatype) * newcapacity); if (!new) { perror(realloc fail); exit(-1); } hp- >_a = new; hp- >_capacity = newcapacity; } hp- >_a[hp- >_size++] = x; adjustup(hp- >_a, hp- >_size - 1);}实现是对于堆的空间进行判断,不够则是扩容操作,当然也有初始化的意思,接着是通过向上调整的方式插入操作。
3.6 堆的删除(较重要)void heappop(heap* hp)//先将最后一个数与堆顶交换,然后再让size--,再进行向下调整{ assert(hp); swap(&hp- >_a[0], &hp- >_a[hp- >_size - 1]); hp- >_size--; adjustdown(hp- >_a, hp- >_size, 0);}进行删除操作,我们当然是删除堆顶啦,这个删除操作先将最后一个数与堆顶交换,然后再让size--,再进行向下调整。
一图让你了解~:
3.7 取堆顶的数据hpdatatype heaptop(heap* hp)//取堆顶{ assert(hp); assert(hp- >_size > 0); return hp- >_a[0];}3.8 堆的数据个数int heapsize(heap* hp)//堆大小{ assert(hp); return hp- >_size;}3.9 堆的判空int heapempty(heap* hp)//判堆空{ assert(hp); return hp- >_size==0;}part4 总体代码4.1pile.h#pragma once#define _crt_secure_no_warnings 01#include#include#include#includetypedefint hpdatatype;typedefstruct heap{ hpdatatype* _a; int _size; int _capacity;}heap;// 堆的构建void heapcreate(heap* hp, hpdatatype* a, int n);// 堆的销毁void heapdestory(heap* hp);// 堆的插入void heappush(heap* hp, hpdatatype x);// 堆的删除void heappop(heap* hp);// 取堆顶的数据hpdatatype heaptop(heap* hp);// 堆的数据个数int heapsize(heap* hp);// 堆的判空int heapempty(heap* hp);4.2pile.c#includepile.hvoid swap(hpdatatype* s1, hpdatatype* s2){ hpdatatype temp = *s1; *s1 = *s2; *s2 = temp;}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 adjustdown(hpdatatype* a, int n, int parent)//向下调整{ int child = parent * 2 + 1; while (child < n) { if (child + 1 a[child])//找出两个孩子中较大的那个,此为大堆,如果要实现小堆则 改 > { ++child; } if (a[child] > a[parent])//此为大堆,如果要实现小堆则 改 > { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } }}void heapcreate(heap* hp, hpdatatype* a, int n){ assert(hp); assert(a); hp- >_a = (hpdatatype*)malloc(sizeof(hpdatatype) * n); if (!hp- >_a) { perror(malloc fail); exit(-1); } hp- >_capacity = hp- >_size = n; //将a中的元素全部转移到堆中 memcpy(hp- >_a, a, sizeof(hpdatatype) * n); //建堆 for (int i = 1; i _a, i);//按向上调整,此建立大堆 }}void heapdestory(heap* hp){ assert(hp); free(hp- >_a); hp- >_a = null; hp- >_capacity = hp- >_size = 0;}void heappush(heap* hp, hpdatatype x){ assert(hp); if (hp- >_capacity == hp- >_size)//扩容 { int newcapacity = hp- >_capacity == 0 ? 4 : hp- >_capacity * 2; hpdatatype* new = (hpdatatype*)realloc(hp- >_a, sizeof(hpdatatype) * newcapacity); if (!new) { perror(realloc fail); exit(-1); } hp- >_a = new; hp- >_capacity = newcapacity; } hp- >_a[hp- >_size++] = x; adjustup(hp- >_a, hp- >_size - 1);}void heappop(heap* hp)//先将最后一个数与堆顶交换,然后再让size--,再进行向下调整{ assert(hp); swap(&hp- >_a[0], &hp- >_a[hp- >_size - 1]); hp- >_size--; adjustdown(hp- >_a, hp- >_size, 0);}hpdatatype heaptop(heap* hp)//取堆顶{ assert(hp); assert(hp- >_size > 0); return hp- >_a[0];}int heapsize(heap* hp)//堆大小{ assert(hp); return hp- >_size;}int heapempty(heap* hp)//判堆空{ assert(hp); return hp- >_size==0;}4.3test.c#includepile.hvoid test(){ heap hp; int arr[] = { 1,6,2,3,4,7,5 }; heapcreate(&hp, arr, sizeof(arr) / sizeof(arr[0])); //heappush(&hp, 10); printf(%dn, heapsize(&hp)); while (!heapempty(&hp)) { printf(%d %d n, heaptop(&hp), heapsize(&hp)); heappop(&hp); } printf(%dn, heapsize(&hp)); heapdestory(&hp); heapsort(arr, sizeof(arr) / sizeof(arr[0])); printf(n);}int main(){ test(); return0;}4.4 测试结果

用FPGA做流水灯
全国产EtherCAT运动控制边缘控制器ZMC432H如何使用Python+QT实现连续轨迹加工
10G DAC和40G光模块在叶脊架构中的应用
布线人的烦恼:超六类网线七类网线如何选择
物联网和全球互联设备正在为互联汽车开拓新的商业模式
堆的实现思路
三星Galaxy S11系列可能会推出三款机型,支持8K视频拍摄
苹果最大最贵双卡双待iPhone正式发布,网友直呼:卖肾也要买
麒麟980定了!余承东:将全球首发7nm手机SoC 性能遥遥领先845
新行业角色:云办公时代,中小微实体企业的数字化转型服务员
苹果正式推送iPadOS13.1 新的布局在每一页上可显示更多app
李开新已经离职,不再担任360手机掌门人
显示屏业务热度依旧,小间距国内市场直逼海外
WCDMA的软搬迁软割接
当今世界谁的5G实力最强_看了就知道
半导体行业拯救者,系统级封装迎来好时光
基于MICRF009的UHF接收器设计
曝台积电将在第二季度末开始量产苹果A14处理器 并还握有苹果5G天线封装订单
富信数字晶体管DTA115E的主要特性
华为P50系列或成为明年最受期待的旗舰手机