堆
概念:
堆通常是一个可以被看作一棵树的数组对象,一个堆是一个几乎完全的二叉树,将根节点最大的堆叫做最大堆,根节点最小的堆叫做最小堆。
堆总是有以下性质:
1.堆中某个节点的值总是不大于(最大堆)或不小于(最小堆)其父节点的值;
2.堆总是一棵完全树。
由以上的定义就可以得知,堆顶元素必为序列中n个元素的最小值或者最大值。
算法思想:
不必将值一个个地插入堆中,而是通过对比交换形成堆。
假设:以最大堆为例,根的左右子树都已是堆,他们的根结点设为R,那么R与左右儿子的值有两种情况:
1.R同时大于或者等于左右儿子,这时候符合堆的特性,所以这时候堆已完成;
2.R可能小于某一个儿子,或者同时大于左右儿子,那么则R应该与左右儿子中较大的一个进行交换,再用同样的方法进行对比交换,直到满足第一个条件,R同时大于或者等于左右儿子为止。
堆的调整:
一.输出堆顶元素后调整剩余元素为一个新堆:
1.输出堆顶元素并以最后一个元素代替;
2.比较左右儿子值的大小;
3.对比后交换;
4.重复步骤直到满足形成新堆的要求为止。
二.加入元素时向上调整:
1.先将堆的总共元素+1;
2.然后将R添加到堆的尾部;
3.根据需要,将R上移,直到满足新堆特性为止。
三.删除元素时向下调整:
1.先将堆的总共元素-1;
2.用堆底元素替代;
3.根据需要,将R下移,直到满足新堆特性为止。
建堆:
给出一个有n个元素的数组,创建一个堆,可以这样进行:
1.从空的堆开始,不断插入一个元素,直到完全转化为堆为止,这种方法创建堆的时间复杂度是O(n logn)。
2.自底向上创建堆:
把一棵n个节点的几乎完全的二叉树转化成堆,从最后一个节点开始到根节点,逐个扫描所有的节点,根据需要,每一次将以当前节点为根节点的子树转化成堆;这种方法创建堆的时间复杂度是O(n)。
堆排序(Heapsort):
由于堆中的各项最大值存储在堆顶元素中,所以每次将A[1](堆顶元素)与A[N](堆底元素)交换,使A[N]成为最大值,最后通过对比交换,形成一个新堆A[1……N-1]。交换元素和调整堆的元素一直重复,知道堆的大小变成1为止。这种方法的时间复杂度为O(n logn)。而如果对n个元素的数组排序,用线性搜索选择排序或者冒泡排序的话,时间复杂度需要O(n^2)时间。
相关资料:
http://www.cnblogs.com/Jason-Damon/archive/2012/04/18/2454649.html
相关推荐
c语言实现 小根堆heap,每次pop的时候都是最小值。整个值以数组形式储存!
基于python的数据结构代码实现-堆Heap
优先队列PriorityQueue,_堆Heap【数据结构和算法入门8】
15年7月最新版的工具Heap Analzer V4。 分析java内存堆快照的利器,拥有直觉性的判断溢出对象是什么,一目了然。支持上下左右键,免去鼠标点击的痛苦。 对象显示也比较详细,数量,大小都包含,支持对象树的复制。
java中堆(heap)和堆栈(stack)有什么区别
用C++和模板实现最大堆,可用于简单排序操作
eager binomial heaps python实现。使用双向链表,make_heap, insert, merge, find_min, extractMin.
通过heapdump工具分析服务器堆分配问题
在clion中对fibonacci heap的完全实现,亲测有效。
堆溢出攻击教程(heap overflow attack)
最近在学习STL的源代码,看到这么多优秀的代码,心里痒痒的,于是自己实现了一遍,当然,有自己的特色,都是模块函数,稍稍用了一些traits特性。相互学习,呵呵
JVM堆分析,Java VM堆分析(节选)。 JProbe 是目前最好的Java性能优化工具之一,在全球有最多的用户。 本文档不但介绍了JProbe的在解决内存问题方面的功能和使用,同时还介绍了必要的Java内存管理的背景知识,深入...
2、堆区(heap)—一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表。3、全局区(静态区)(static)—全局变量和静态变量的存储是放在一块...
c++ code for MaxHeap Sort
Visual C++ 小内存堆(Small Block Heap)问题
ibm-java-堆内存分析工具-heapanalyzer
Heap堆解题套路【LeetCode刷题套路教程6】
David Litchfield课件 源码c语言
void heap_sort(int A[],int length) { BUILD_MAX_HEAP(A,length); int i,middle; for(i=length-1;i>0;i--) { middle=A[0]; A[0]=A[i]; A[i]=middle; heap_size--; MAX_HEAPIFY(A,0); } }
二项堆(Binomial Heap)的c语言完全实现,包括添加,删除,和找到最小值,删除最小值