c 数据结构之堆的概念是什么-亚博电竞手机版

c 数据结构之堆的概念是什么

今天小编给大家分享一下c 数据结构之堆的概念是什么的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。

堆的概念

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象，即是一种顺序储存结构的完全二叉树。

提示：完全二叉树

完全二叉树：对一棵深度为k、有n个结点二叉树编号后，各节点的编号与深度为k的满二叉树相同位置的结点的编号相同，这颗二叉树就被称为完全二叉树。[2]

堆的性质

• 堆中某个结点的值总是不大于或不小于其父结点的值

• 堆总是一棵完全二叉树

• 除了根结点和最后一个左子结点可以没有兄弟结点，其他结点必须有兄弟结点

最大堆最小堆

• 最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。

• 最小堆：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。

代码

定义

有限数组形式

intheap[1024];//顺序结构的二叉树

若某结点编号为i，且存在左儿子和右儿子，则他们分别对应

heap[i*2 1];//左儿子heap[i*2 2];//右儿子

其父节点

heap[i/2];//i的父节点

动态数组形式

在项目开发中，经常以动态数组形式出现，在本文主要对这种形式进行介绍

//默认容量#definedefault_capcity128typedefstruct_heap{int*arr;//储存元素的动态数组intsize;//元素个数intcapacity;//当前存储的容量}heap;

操作

只使用initheap()函数进行初始化即可，adjustdown()与buildheap()仅为堆建立时的内部调用

向下调整结点

• 以创建最大堆为例

• 将“判断最大子结点是否大于当前父结点”处的>=改为<=即可创建最小堆

//向下调整，将当前结点与其子结点调整为最大堆//用static修饰禁止外部调用staticvoidadjustdown(heap&heap,intindex){intcur=heap.arr[index];//当前待调整结点intparent,child;/*判断是否存在子结点大于当前结点。若不存在，堆是平衡的，则不调整；若存在，则与最大子结点与之交换，交换后该子节点若还有子结点，则以此方法继续调整。*/for(parent=index;(parent*2 1)=heap.arr[child])//将此处的>=改成<=可构建最小堆{//不大于，不需要调整break;}else{//大于，则交换heap.arr[parent]=heap.arr[child];heap.arr[child]=cur;}}}

建立堆

//建立堆，用static修饰禁止外部调用staticvoidbuildheap(heap&heap){inti;//从倒数第二层开始调整（若只有一层则从该层开始）for(i=heap.size/2-1;i>=0;i--){adjustdown(heap,i);}}

初始化

//初始化堆//参数：被初始化的堆，存放初始数据的数组，数组大小boolinitheap(heap&heap,int*orginal,intsize){//若容量大于size，则使用默认量，否则为sizeintcapacity=default_capcity>size?default_capcity:size;heap.arr=newint[capacity];//分配内存，类型根据实际需要可修改if(!heap.arr)returnfalse;//内存分配失败则返回falseheap.capacity=capacity;//容量heap.size=0;//元素个数置为0//若存在原始数组则构建堆if(size>0){/*内存拷贝，将orginal的元素拷贝到堆数组arr中size*sizeof(int)为元素所占内存空间大小*/memcpy(heap.arr,orginal,size*sizeof(int));heap.size=size;//调整大小buildheap(heap);//建堆}returntrue;}

打印堆

• 实际上是一个层序遍历[4]

//以树状的形式打印堆voidprintheapastreestyle(heaphp){queueque;intr=0;que.push(r);queuetemp;while(!que.empty()){r=que.front();que.pop();if(r*2 1();}elsecout<

测试

main函数

intmain(){heaphp;intvals[]={1,2,3,87,93,82,92,86,95};if(!initheap(hp,vals,sizeof(vals)/sizeof(vals[0]))){fprintf(stderr,"初始化堆失败！\n");exit(-1);}printheapastreestyle(hp);return0;}

结果

959392871823862

完整代码

#include#includeusingnamespacestd;//默认容量#definedefault_capcity128typedefstruct_heap{int*arr;intsize;intcapacity;}heap;//向下调整，将当前结点与其子结点调整为最大堆staticvoidadjustdown(heap&heap,intindex){intcur=heap.arr[index];//当前待调整结点intparent,child;/*判断是否存在子结点大于当前结点。若不存在，堆是平衡的，则不调整；若存在，则与最大子结点与之交换，交换后该子节点若还有子结点，则以此方法继续调整。*/for(parent=index;(parent*2 1)=heap.arr[child])//将此处的>=改成<=可构建最小堆{//不大于，不需要调整break;}else{//大于，则交换heap.arr[parent]=heap.arr[child];heap.arr[child]=cur;}}}//建立堆，用static修饰禁止外部调用staticvoidbuildheap(heap&heap){inti;//从倒数第二层开始调整（若只有一层则从该层开始）for(i=heap.size/2-1;i>=0;i--){adjustdown(heap,i);}}//初始化堆//参数：被初始化的堆，存放初始数据的数组，数组大小boolinitheap(heap&heap,int*orginal,intsize){//若容量大于size，则使用默认量，否则为sizeintcapacity=default_capcity>size?default_capcity:size;heap.arr=newint[capacity];//分配内存，类型根据实际需要可修改if(!heap.arr)returnfalse;//内存分配失败则返回falseheap.capacity=capacity;//容量heap.size=0;//元素个数置为0//若存在原始数组则构建堆if(size>0){/*内存拷贝，将orginal的元素拷贝到堆数组arr中size*sizeof(int)为元素所占内存空间大小*/memcpy(heap.arr,orginal,size*sizeof(int));heap.size=size;//调整大小buildheap(heap);//建堆}returntrue;}//以树状的形式打印堆voidprintheapastreestyle(heaphp){queueque;intr=0;que.push(r);queuetemp;while(!que.empty()){r=que.front();que.pop();if(r*2 1();}elsecout<

以上就是“c 数据结构之堆的概念是什么”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注恰卡编程网行业资讯频道。