要说最大堆和最小堆,就得先知道最大树和最小树。
每个结点的值都大于(小于)或等于其子节点(如果有的话)值的树,就叫最大(最小)树。
最大堆(最小堆)是最大(最小)完全树。
由于堆是完全二叉树,所以可以用公式化描述,用一维数组来有效的描述堆结构。
利用二叉树的性质:
如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第[log2n]向下取整+1层,每层从左到右),则对任一结点i(1≤i≤n),有:
(1)如果i=1,则结点i无双亲,是二叉树的根;如果i>1,则其双亲是结点[i/2]向下取整。
(2)如果2i>n,则结点i为叶子结点,无左孩子;否则,其左孩子是结点2i。
(3)如果2i+1>n,则结点i无右孩子;否则,其右孩子是结点2i+1。
这样就就可以将堆中结点移到它的父节点或者其中一个子节点处。
堆中进行的操作主要是:插入,删除,以及初始化。
下面只讨论最大堆。
在最大堆中进行插入操作,例如在下图所示的左边的最大堆中进行插入,插入后结构应该是和右边的图一样的。
插入时,现将新元素从新堆的父节点开始比较,也就是先从2所在结点开始比较,如果小于父节点的值,那么就直接作为孩子结点插入,如果大于,那么就要现将父节点下移,然后再和父节点的父节点比较,一直比较到根节点为止,所以插入过程,是从叶节点到根的一条路径。
最大堆的删除,从最大堆的删除时,该元素从根部移出。删除后,此时堆需要重新构造,以便于仍然为完全二叉树。例如下图:
先将根节点的值20取出后,为了结构仍然是二叉树,所以直接将最后一个结点,也就是保存2的结点去掉,然后将2的值保存下来,然后呢,就从根节点的两个孩子开始比较,看看2 根的左右孩子,这三个元素中,谁最大,那么根节点的值就是谁,然后就将2和空出来的结点的左右孩子(如果有的话)比较,确认子树的根节点的值,这样一步一步确认下去。
用数组初始化堆,数组元素显示按照下面的顺序,一个一个放在结点中
然后就从最后一个父节点开始,就是第五个结点,10所在的位置啦,从那里开始构造以该节点为根的最大堆。构造好后就移到下一个结点,15所在结点,以此类推,一直到根节点。
下面是代码:
文件"maxheap.h"
测试文件"main.cpp"
测试结果:
在只是需要使用一个优先队列的时候,这种结构是十分有效率的,空间利用率也很高。但是并不适用于所有优先队列的使用,尤其是需要合并两个优先队列或多个长度不相等的队列的时候。
分享到:
相关推荐
数组堆的实现 堆的实现 c++实现 支持自定义值类型、自定义用于比较的函数对象
功能包括创建最大堆,插入和删除元素,判断空堆满堆,重载了用于输出,输出的形式是广义表. 还有堆的析构函数忘记写了 应该在程序中添加 ~MaxHeap() { delete [] heap; } 另外,MaxFQ虚类中的Full(),IsFull(),Empty(),...
1.线性表:数据存储像一条线一样的结构,每个线性表上的数据最多只有前和后的两个方向,如数组、链表、队列、栈等都是这种结构,所以实现的数组的动态操作,其他结构也可轻易的类似实现。更重要的是,在这之后看源码...
二、数据结构的实现 16 1、二叉树三种遍历的非递归算法 16 1.先序遍非递归算法 16 2.中序遍历非递归算法 17 3.后序遍历非递归算法 18 4.层次遍历算法 19 2、线性表 20 4、串 23 5、多维数组和广义表 24 6、树与...
队列_基于动态数组实现 3.2.LinkedListQueue .................. 队列__基于链表实现 3.3.LoopQueue ........................... 循环队列_基于动态数组实现 3.4.PriorityQueue ....................... 优先队列_...
11.7.2 指向结构数组的指针 179 11.7.3 结构指针变量作函数参数 180 11.8 动态存储分配 181 11.9 链表的概念 182 11.10 枚举类型 184 11.10.1 枚举类型的定义和枚举变量的说明 184 11.10.2 枚举类型变量的赋值和使用...
我将用c++实现一个堆来简单分析一下。 堆排序的基本思想为: 1、升序排列,保持大堆;降序排列,保持小堆; 2、建立堆之后,将堆顶数据与堆中最后一个数据交换,堆大小减一,然后向下调整;直到堆中只剩下一个有效值...
MCU_51_结构数组_结构与函数.mp4 MCU_51_联合.mp4 PonC_指针和数组-2.mp4 VSE_6_安装.mp4 VS_2008_速成版_下载和安装.mp4 大家可以学的C语言 ABG2C_Cpp_更强大的C.mp4 ABG2C_for_循环.mp4 ABG2C_两个预...
11.7.2 指向结构数组的指针 179 11.7.3 结构指针变量作函数参数 180 11.8 动态存储分配 181 11.9 链表的概念 182 11.10 枚举类型 184 11.10.1 枚举类型的定义和枚举变量的说明 184 11.10.2 枚举类型变量的赋值和使用...
用的是数组存储的最大堆元素,最大堆类继承自完全二叉树和最大优先队列两个类. 重载了操作符,方便输出. 其他必要的功能也提供了.
C++标准库实现简介 C++标准库是一组C++模板类,提供了通用的编程数据结构和函数,如链表、堆、数组、算法、迭代器等C++组件。C ++标准库包含了C标准库,并在C++标准中进行了定义。 C++编译器开发厂商根据C++标准委员会...
C++模板类实现的动态数组、双向循环链表、队列、栈等数据结构,以及基于迭代器的静态查找和排序算法,包括顺序查找、折半查找、简单选择排序(用于单向迭代器)、快速排序(双向迭代器)、堆排序(随机迭代器)。...
算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。这些代码不仅能帮助你理解数据结构的基本概念,而且能让你明白如何在实际情况中应用这些数据结构。 笔记:详细且系统的笔记,...
5.5 在一个数组中实现的多重表 5.6 性能测量 5.7 参考及推荐读物 第6章 线性表——链式描述 6.1 单向链表 6.1.1 描述 6.1.2 结构chainNode 6.1.3 类chain 6.1.4 抽象数据类型linearList的扩充 6.1.5 类extendedChain...
数据结构–用C++实现循环顺序队列 队列的操作特性:先进先出 队列中元素具有相同类型 相邻元素具有前驱和后继关系 设置队头、队尾两个指针,以改进出队的时间性能 约定:队头指针front指向队头元素的前一个位置...
约翰逊算法使用各种数据结构,例如二进制堆,二项式堆,斐波那契堆阵列,实现了Johnson算法(全对最短路径)。
这些代码主要是针对严蔚敏老师的《数据结构》一书中的大部分伪代码编辑的代码,能够正常运行,是基于C++编写的代码,包括,数组线性表,链表线性表、双向链表、顺序栈、链栈、链队列,顺序队列,循环队列、KMP算法、...
本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...
4.1.2 C++数组 129 4.1.3 行主映射和列主映射 129 4.1.4 类Array1D 131 4.1.5 类Array2D 133 4.2 矩阵 137 4.2.1 定义和操作 137 4.2.2 类Matrix 138 4.3 特殊矩阵 141 4.3.1 定义和应用 141 4.3.2 对角矩阵 143 ...