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

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

堆的概念

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

提示：完全二叉树

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

堆的性质

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

• 堆总是一棵完全二叉树

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

最大堆最小堆

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

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

代码

定义

有限数组形式

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

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

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

其父节点

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

动态数组形式

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

//默认容量#define DEFAULT_CAPCITY 128typedef struct _Heap{int *arr;//储存元素的动态数组int size;//元素个数int capacity;//当前存储的容量}Heap;

操作

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

向下调整结点

• 以创建最大堆为例

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

//向下调整，将当前结点与其子结点调整为最大堆//用static修饰禁止外部调用static void AdjustDown(Heap& heap, int index){int cur = heap.arr[index];//当前待调整结点int parent, 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修饰禁止外部调用static void BuildHeap(Heap& heap){int i;//从倒数第二层开始调整（若只有一层则从该层开始）for (i = heap.size / 2 - 1; i >= 0; i--){AdjustDown(heap, i);}}

初始化

//初始化堆//参数：被初始化的堆，存放初始数据的数组， 数组大小bool InitHeap(Heap &heap, int *orginal, int size){//若容量大于size，则使用默认量，否则为sizeint capacity = DEFAULT_CAPCITY>size?DEFAULT_CAPCITY:size;heap.arr = new int[capacity];//分配内存，类型根据实际需要可修改if(!heap.arr) return false;//内存分配失败则返回Falseheap.capacity = capacity;//容量heap.size = 0;//元素个数置为0//若存在原始数组则构建堆if(size>0){memcpy(heap.arr,orginal, size*sizeof(int));heap.size = size;//调整大小BuildHeap(heap);//建堆}return true;}

打印堆

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

//以树状的形式打印堆void PrintHeapAsTreeStyle(Heap hp){queue<int> que;int r = 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函数

int main(){Heap hp;int vals[] = { 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);return 0;}

结果

9593 9287 1 82 386 2

完整代码

#include <iOStream>#include <queue>using namespace std;//默认容量#define DEFAULT_CAPCITY 128typedef struct _Heap {int* arr;int size;int capacity;}Heap;//向下调整，将当前结点与其子结点调整为最大堆static void AdjustDown(Heap& heap, int index){int cur = heap.arr[index];//当前待调整结点int parent, 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修饰禁止外部调用static void BuildHeap(Heap& heap){int i;//从倒数第二层开始调整（若只有一层则从该层开始）for (i = heap.size / 2 - 1; i >= 0; i--){AdjustDown(heap, i);}}//初始化堆//参数：被初始化的堆，存放初始数据的数组， 数组大小bool InitHeap(Heap& heap, int* orginal, int size){//若容量大于size，则使用默认量，否则为sizeint capacity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size;heap.arr = new int[capacity];//分配内存，类型根据实际需要可修改if (!heap.arr) return false;//内存分配失败则返回Falseheap.capacity = capacity;//容量heap.size = 0;//元素个数置为0//若存在原始数组则构建堆if (size > 0){memcpy(heap.arr, orginal, size * sizeof(int));heap.size = size;//调整大小BuildHeap(heap);//建堆}return true;}//以树状的形式打印堆void PrintHeapAsTreeStyle(Heap hp){queue<int> que;int r = 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] << " ";}}int main(){Heap hp;int vals[] = { 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);return 0;}

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