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.size;parent=child){child=parent*2+1;//左子结点//取两个子结点中最大节点,(child+1)<heap.size防止越界if(((child+1)<heap.size&&(heap.arr[child]<heap.arr[child+1])))child++;//判断最大子结点是否大于当前父结点if(cur>=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){queue<int>que;intr=0;que.push(r);queue<int>temp;while(!que.empty()){r=que.front();que.pop();if(r*2+1<hp.size)temp.push(r*2+1);if(r*2+2<hp.size)temp.push(r*2+2);if(que.empty()){cout<<hp.arr[r]<<endl;que=temp;temp=queue<int>();}elsecout<<hp.arr[r]<<"";}}
测试
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<iostream>#include<queue>usingnamespacestd;//默认容量#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.size;parent=child){child=parent*2+1;//左子结点//取两个子结点中最大节点,(child+1)<heap.size防止越界if(((child+1)<heap.size&&(heap.arr[child]<heap.arr[child+1])))child++;//判断最大子结点是否大于当前父结点if(cur>=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){queue<int>que;intr=0;que.push(r);queue<int>temp;while(!que.empty()){r=que.front();que.pop();if(r*2+1<hp.size)temp.push(r*2+1);if(r*2+2<hp.size)temp.push(r*2+2);if(que.empty()){cout<<hp.arr[r]<<endl;que=temp;temp=queue<int>();}elsecout<<hp.arr[r]<<"";}}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;}
以上就是“C++数据结构之堆的概念是什么”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注恰卡编程网行业资讯频道。
