龙华做网站公司,好的网站设计制作,wordpress picasa,无锡网站建设818gx堆的特性#xff1a;
必须是完全二叉树 用数组实现 任一结点的值是其子树所有结点的最大值或最小值 最大值时#xff0c;称为“最大堆”#xff0c;也称大根堆#xff1b;
在完全二叉树中#xff0c;任何一个子树的最大值都在这个子树的根结点。最小值时#xff0c;称为…堆的特性
必须是完全二叉树 用数组实现 任一结点的值是其子树所有结点的最大值或最小值 最大值时称为“最大堆”也称大根堆
在完全二叉树中任何一个子树的最大值都在这个子树的根结点。最小值时称为“最小堆”也称小根堆。
在完全二叉树中任何一个子树的最小值都在这个子树的根结点。大根堆 小根堆 可以看到对于**堆Heap**这种数据结构从根节点到任意结点路径上所有的结点都是有序的。
整理 二叉堆
逻辑上完全二叉树
存储上数组顺序存储
作用找最值 优先级队列操作
1向下调整 * 建队删除
2建堆
3向上调整 插入数据结构中堆与内存堆区的区别
一、数据结构中的堆和栈 堆和栈在数据结构中是两种不同的数据结构。 两者都是数据项按序排列的数据结构。栈像是装数据的桶或者箱子栈是大家比较熟悉的一种数据结构它是一种具有后进先出的数据结构也就是说后存放的先取先存放的后取这就类似于我们要在取放在箱子底部的东西放进去比较早的物体我们首先要移开压在它上面的物体放入比较晚的物体。堆像是一颗倒立的大树堆是一种经过排序的树形数据结构每个节点都有一个值。通常我们所说的堆的数据结构是指二叉树。堆的特点是根节点的值最小或最大且根节点的两个树也是一个堆。由于堆的这个特性常用来实现优先队列堆的存取是随意的这就如同我们在图书馆的书架上取书虽然书的摆放是有顺序的但是我们想取任意一本时不必像栈一样先取出前面所有的书书架这种机制不同于箱子我们可以直接取出我们想要的书。二、内存分配中的堆和栈 我们现在经常用的并不是数据结构中的堆和栈之所以说了数据结构中的堆和栈是为了和后面将要说的堆区和栈区区别开来请大家一定要注意。内存中的栈区处于相对较高的地址以地址的增长方向为上的话栈地址是向下增长的。栈中分配局部变量空间堆区是向上增长的用于分配程序员申请的内存空间。另外还有静态区是分配静态变量全局变量空间的。只读区是分配常量和程序代码空间的以及其他一些分区。来看一个很经典的例子
main.cppint a 0; 全局初始化区char *p1; 全局未初始化区main (){int b; 栈char s[] “abc”;栈char *p2; 栈char *p3 “123456”; 123456\0 在常量区p3 在栈区static int c 0 全局静态初始化区p1 (char *)malloc(10);堆p2 (char *)malloc (20);堆}三 、 内存分配中栈区和堆区的区别
0、申请方式和回收方式不同 不知道你是否有点明白了堆和栈的第一个区别就是申请方式的不同栈英文名字;stack是系统自动分配空间的例如我们定义了一个 char a 系统会自动的在栈上为其开辟空间。而堆英文名字:heap则是程序员根据需要自己申请的空间例如malloc(10); 开辟是个字节的空间。由于栈上的空间是自动分配自动回收的所以栈上的数据的生存周期只是在函数的运行过程中运行后就释放掉不可以再访问。而堆上的数据只要程序员不释放空间就一直可以访问到不过缺点是一旦忘记释放会造成内存泄露。
1、 申请后系统的响应 栈 只要栈的剩余空间大于所申请的空间系统将为程序提供内存否则将报异常提示栈溢出。堆首先应该知道操作系统有一个记录空闲内存地址的链表当系统受到程序的申请时会遍历该链表寻找第一个空间大于所申请空间的堆。结点然后将该结点从空闲结点链表中删除并将该结点的空间分配给程序另外对于大多数系统会在这块内存空间中的首地址处记录本次分配的大小这样代码中的delete语句才能正确的释放本内存空间。另外由于找到的堆结点的大小不一定正好等于申请的大小系统会自动的将多余的那部分重新放入空闲链表中。也就是说堆会在申请后还要做一些后续的工作这就会引出申请效率的问题2、申请效率的比较
栈 由系统自动分配速度较快。但程序员是无法控制的。堆 是由new分配的内存一般速度比较慢而且容易产生内存碎片不过用起来最方便。3、 申请大小的限制
栈 在Windows下栈是向低地址扩展的数据结构是一块连续的内存的区域。
这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的
在Windows下栈的大小是2M也有的说是1M总之是一个编译时就确定的常数
如果申请的空间超过栈的剩余空间时将提示overflow。因此能从栈获得的空间较小。堆堆是向高地址扩展的数据结构是不连续的内存区域。这是由于系统是用链表来存储空闲内存地址的自然是不连续的而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见堆获得的空间比较灵活也比较大。4、堆和栈中的内存内容 由于栈的大小限制所以用子函数还是有物理意义的而不仅仅是逻辑意义。栈在函数调用时第一个进栈的是主函数中函数调用后的下一条指令函数调用语句的吓一跳可执行语句的地址
然后是函数的各个参数在大多数的C编译器中参数是有右往左入栈的然后是函数中的局部变量。
注意静态变量是不入栈的。
当本次函数调用结束后局部变量先出栈然后是参数最后栈顶指针指向最开始存的地址
也就是主函数中的下一条指令程序由该点继续运行。堆一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。
5、 关于堆和栈一个比较形象的比喻
栈使用栈就像我们去饭馆里吃饭只管点菜发出申请、付钱、吃使用吃饱了就走
不必理会切菜洗菜等准备工作和洗碗、刷锅等扫尾工作他的好处就是快捷但是自由度小。堆使用堆就像是自己动手做喜欢的菜肴比较麻烦但是比较符合自己的口味而且自由度大此处参考了博客http://blog.csdn.net/wolenski/article/details/7951961#comments
堆的基本操作
堆就是完全二叉树 而完全二叉树其实就是数组你可以把它想象成一个完全二叉树。在数组中定义一个规则 规则 左 2i1 右 2i2 父 (i-1)/2
大根堆的向下调整
1每回数组中进来一个树把它与父结点进行比较如果比他大就交换
2找父结点进来的数在数组中的下标i-1/2就是父结点的位置堆的操作
堆的向下调整 建堆
小堆的建立 从最后一个非叶子节点开始不断的向下调整。
向上调整
