因为vs2005中c++的Heap构造有些问题,所以才重写了heap类。
不知道vs2008中这个是不是个bug。
-
-
template<classT,classCmp>
-
classHeap
- {
-
private:
- vector<T>heap;
-
voidShiftDown(intindex)
- {
-
while(!IsLeaf(index))
- {
-
intl=Lchild(index);
-
intr=Rchild(index);
-
if(r!=-1)
- {
-
if(Cmp::Up(heap[r],heap[l]))
- {
-
- swap(heap[l],heap[r]);
- }
- }
-
if(Cmp::Up(heap[l],heap[index]))
- {
-
- swap(heap[l],heap[index]);
- index=l;
- }
-
else
- {
-
break;
- }
- }
- }
-
voidShiftUp(intindex)
- {
-
intparent=-1;
-
while(index!=0)
- {
- parent=Parent(index);
-
if(Cmp::Up(heap[index],heap[parent]))
- {
- swap(heap[index],heap[parent]);
- index=parent;
- }
-
else
- {
-
break;
- }
- }
- }
-
voidReHeapAll()
- {
-
for(inti=Parent(heap.size()-1);i>=0;i--)
- {
- ShiftDown(i);
- }
- }
-
voidReHeapOne(intindex)
-
- {
- Tdata=heap[index];
- ShiftDown(index);
-
if(Cmp::Eq(data,heap[index]))
- {
- ShiftUp(index);
- }
- }
-
intParent(intindex)
-
- {
-
return(index-1)/2;
- }
-
intLchild(intindex)
-
- {
-
if(!IsLeaf(index))
-
returnindex*2+1;
-
return-1;
- }
-
intRchild(intindex)
-
- {
-
if(!IsLeaf(index))
- {
-
intr=index*2+2;
-
if(r<heap.size())
-
returnr;
- }
-
return-1;
- }
-
intIsLeaf(intindex)
- {
- assert(index<heap.size());
-
if(heap.size()==1)
-
returntrue;
-
intlastNode=Parent(heap.size()-1);
-
returnlastNode<index;
- }
-
intFindData(T&data)
- {
-
intlen=heap.size();
-
for(inti=0;i<len;i++)
- {
-
if(Cmp::Eq(data,heap[i]))
- {
-
returni;
- }
- }
-
return-1;
- }
-
voidprintTree(intindex,intcount)
- {
-
if(index<heap.size()&&index>=0)
- {
- printTree(Rchild(index),count+4);
-
for(inti=0;i<count;i++)
- {
-
cout<<"";
- }
- cout<<heap[index]<<endl;
- printTree(Lchild(index),count+4);
- }
- }
-
public:
- Heap()
- {
- heap=vector<T>();
- }
- ~Heap()
- {
-
- }
-
boolIsEmpty()
- {
-
returnheap.size()==0;
- }
-
voidInsert(T&data)
- {
- heap.push_back(data);
- ShiftUp(heap.size()-1);
- }
-
voidDelete(intindex)
- {
-
intlast=heap.size()-1;
-
if(index>=0&&index<=last)
- {
- swap(heap[index],heap[last]);
- heap.pop_back();
- ReHeapOne(index);
- }
- }
-
voidDelete(T&data)
- {
-
intindex=FindData(data);
-
if(index!=-1)
- Delete(index);
- }
-
voidRemoveTop()
- {
-
if(!IsEmpty()&&heap.size()>1)
- {
- swap(heap[0],heap[heap.size()-1]);
- heap.pop_back();
- ShiftDown(0);
- }
-
elseif(heap.size()==1)
- {
- heap.pop_back();
- }
- }
- T&Top()
- {
-
returnheap[0];
- }
-
voidPrint()
- {
- printTree(0,1);
- }
- };
分享到:
相关推荐
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); } }
eager binomial heaps python实现。使用双向链表,make_heap, insert, merge, find_min, extractMin.
Heap Shot是 jQuery的堆叠图像画廊插件,含INCLUDE JS&CSS、HTML、初始化JS代码。大家可以参考学习 一下,效果很炫呢。 建议开发童鞋使用统一开发环境UDE来进行查看、调试、开发~~~统一开发环境是一款HTML5跨平台一...
c语言实现 小根堆heap,每次pop的时候都是最小值。整个值以数组形式储存!
15年7月最新版的工具Heap Analzer V4。 分析java内存堆快照的利器,拥有直觉性的判断溢出对象是什么,一目了然。支持上下左右键,免去鼠标点击的痛苦。 对象显示也比较详细,数量,大小都包含,支持对象树的复制。
基于python的数据结构代码实现-堆Heap
优先队列PriorityQueue,_堆Heap【数据结构和算法入门8】
lazy binomial heaps的oython实现,优先队列。采用双向循环链表实现,api:merge,insert,find_min,extractMin,coalesce_step,updateMin。
java中堆(heap)和堆栈(stack)有什么区别
heapdump分析工具------HeapAnalyzer: 2014年1月最新发布 用法: 在命令行执行 java -Xmx500m -jar ha453.jar
用C++和模板实现最大堆,可用于简单排序操作
游戏编程high performance heap allocator
通过heapdump工具分析服务器堆分配问题
heap Analyzer heapdump分析工具
在clion中对fibonacci heap的完全实现,亲测有效。
堆溢出攻击教程(heap overflow attack)
IBM的HeapAnalyzer IBM的HeapAnalyzer IBM的HeapAnalyzer
最近在学习STL的源代码,看到这么多优秀的代码,心里痒痒的,于是自己实现了一遍,当然,有自己的特色,都是模块函数,稍稍用了一些traits特性。相互学习,呵呵
2、堆区(heap)—一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表。3、全局区(静态区)(static)—全局变量和静态变量的存储是放在一块...
JVM堆分析,Java VM堆分析(节选)。 JProbe 是目前最好的Java性能优化工具之一,在全球有最多的用户。 本文档不但介绍了JProbe的在解决内存问题方面的功能和使用,同时还介绍了必要的Java内存管理的背景知识,深入...