1. A heap is a container for objects that have keys. Supported Operations:
a) Insert ---- Add a new object to a heap. Running time : (O(logn))
b) Extract-Min ---- remove an object in heap with a minimum key value. Running time : (O(logn))
c) Heapfy ---- n batched Inserts in O(n) time.
d) Delete ---- delete an object from heap. Running time : (O(logn))
2. Canonical use of heap: fast way to do repeated minimum computations.
3. Application: Sorting
SelectionSort : ~ O(n) linear scans, O(n^2) runtime on array of length n
Heap Sort : 1) insert all n array elements into a heap
2) Extract-Min to pluck out elements in sorted order
Running Time = 2n heap operations = O(nlog(n)) time.
4. Application: Event Manager
“Priority Queue” – synonym for a heap.
-- Objects = event records ( Action/update to occur at given time in the future )
-- Key = time event scheduled to occur
-- Extract-Min => yields the next scheduled event
5. Application: Median Maintenance
Input: a sequence x1, x2, ..., xn of numbers, one-by-one
Output: at each step i , the median of {x1, .., xi}.
Constraint: use O(log(i)) time at each step i.
Solution: maintain heaps invariants
a) Hlow = i/2 smallest elements and support Extract Max
b) Hhigh = i/2 largest elements and support Extract Min
Claim 1) can maintain invariants in O(log(i)) time
2) given invariant, can compute median in O(log(i)) time
6. Heap Implementation:
a) Think of a heap as a tree, rooted, binary, as complete as possible
b) At every node x, Key[x] <= all keys of x’s children
c) Object at root must have minimum key value
d) Array Implementation: Parent(i) = floor(i/2) , Children(i) = 2i, 2i+1
e) Insert (k)
- stick k at end of last level.
- Bubble-Up k until heap property is restored (key of k’s parent <= k)
f) Extract-Min
- Delete root
- Move last leaf to be new root.
- Iteratively Bubble-Down until heap property has been restored [always swap with smaller child!]
相关推荐
使用方法如下: ...python native_heapdump_viewer.py --symbols symbols 00.txt >00.log python native_heapdump_viewer.py --symbols symbols 01.txt >01.log 对比00.log和01.log,查看内存增长的点
heapdump分析工具------HeapAnalyzer: 2014年1月最新发布 用法: 在命令行执行 java -Xmx500m -jar ha453.jar
IBM的HeapAnalyzer IBM的HeapAnalyzer IBM的HeapAnalyzer
通过heapdump工具分析服务器堆分配问题
heap Analyzer heapdump分析工具
ibm的heap analyzer.zip
1,IBM的HeapAnalyzer工具。在我们的应用程序发生内存泄露的时候,会生成heapdump文件 2,IBM的Thread and Monitor Dump Analyzer for Java工具 在一些平台上,在有些情况下,javacore也被称为javadump,它包含jvm和...
could not reserve enough space for object heap
oracle:Heap size 3597K exceeds notification threshold 解决方法
java.lang.OutOfMemoryError: Java heap space 解决方法
heapdump文件分析工具(最新2012-12-18) 用于分析OOM内存溢出的错误
解决Java_heap_space问题
搜集整理关于java错误处理:java.lang.OutOfMemoryError: Java heap space java.lang.OutOfMemoryError: Java heap space 资料整理
heapdump分析工作heapanalyzer的使用及工具 java -Xmx1000m -jar ha443.jar
Myeclipse下java.lang.OutOfMemoryError Java heap space的解决
IBM HeapAnalyzer 最新版本 java内存分析工具,性能调优,内存泄露排除比不可少的工具
解决报错HEAP CORRUPTION DETECTED heap corruption detected after normal block.zip
ibm HeapAnalyzer JVM内存分析工具 ha457.jar下载