`
leonzhx
  • 浏览: 794024 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论
阅读更多

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!]

 

 

分享到:
评论

相关推荐

    IBM的HeapAnalyzer

    IBM的HeapAnalyzer是一款强大的内存分析工具,主要用于诊断Java应用程序中的内存泄漏问题。它能帮助开发者深入理解Java虚拟机(JVM)的堆内存状态,通过分析heap dump文件,找出那些占用内存过大的对象,以及这些...

    heapdump分析工具

    当遇到应用程序运行缓慢,频繁出现Full GC,甚至出现OutOfMemoryError等问题时,我们通常需要对堆内存进行深入分析,这就是heapdump工具的作用所在。heapdump工具可以帮助开发者诊断Java应用的内存泄漏、过度对象...

    heapdump-tool工具

    【标题】:heapdump-tool工具 【正文】: 在IT领域,内存管理是优化系统性能的关键环节,尤其是在Java应用程序中。Heapdump-tool工具是专为Java开发者设计的,用于生成和分析堆转储(Heap Dump)文件的强大工具。...

    Heap Dump的IBM分析工具.zip

    "Heap Dump的IBM分析工具.zip" 提供了一个专门用于解析和分析heap dump的IBM工具,帮助我们更好地理解JVM内存的状态。 Heap dump文件是Java虚拟机(JVM)在特定时间点生成的一种文件,它包含了JVM堆内存中的所有...

    java 内存溢出分析工具 HeapAnalyzer

    HeapAnalyzer是一款强大的工具,专为分析Java应用程序的内存状况,特别是针对内存溢出问题进行诊断。本文将详细介绍HeapAnalyzer的使用、功能以及如何通过它来排查和解决Java OOM问题。 一、HeapAnalyzer简介 Heap...

    IBM WEBSPHERE heapdump分析工具 ha456

    "heapdump"是一种重要的诊断手段,它能记录下JVM(Java虚拟机)在某一时刻的内存状态。本篇文章将详细介绍如何利用IBM WebSphere生成heapdump以及使用分析工具"ha456"进行故障排查。 首先,让我们理解heapdump的...

    native_heapdump_viewer.py

    使用方法如下: ...python native_heapdump_viewer.py --symbols symbols 00.txt &gt;00.log python native_heapdump_viewer.py --symbols symbols 01.txt &gt;01.log 对比00.log和01.log,查看内存增长的点

    ibm的heap analyzer.zip

    IBM Heap Analyzer是一款强大的内存分析工具,主要用于Java应用程序的性能优化,特别是针对IBM J9 JVM的内存管理和垃圾收集进行深入分析。这款工具可以帮助开发者诊断和解决内存泄漏、过度对象分配以及垃圾收集效率...

    ibm-java-堆内存分析工具-heapanalyzer

    IBM Java堆内存分析工具——HeapAnalyzer,是一款专为IBM J9 VM设计的强大内存分析工具,它可以帮助开发者深入理解Java应用程序的内存使用情况,检测并解决内存泄漏问题,从而提升应用性能。本文将详细介绍Heap...

    ibm HeapAnalyzer JVM内存分析工具 ha457.jar下载

    IBM HeapAnalyzer是一款强大的Java虚拟机(JVM)内存分析工具,专为诊断和解决Java应用程序的内存泄漏问题而设计。这个工具能够帮助开发者深入理解Java应用程序的内存使用情况,从而优化性能并防止由于内存泄漏导致...

    heapdump分析工具HeapAnalyzer

    heapdump分析工具------HeapAnalyzer: 2014年1月最新发布 用法: 在命令行执行 java -Xmx500m -jar ha453.jar

    内存泄露分析工具(IBM HeapAnalyzer 和 Pattern Modeling and Analysis )

    IBM HeapAnalyzer和Pattern Modeling and Analysis (PMA)是两种强大的工具,专门用于诊断和解决这类问题。 IBM HeapAnalyzer是一款强大的内存分析工具,主要用于分析Java应用的堆内存。当应用程序出现内存泄漏时,...

    oracle:Heap size 3597K exceeds notification threshold

    ### Oracle:“Heap size 3597K exceeds notification threshold” 解决方案 #### 背景与问题描述 在Oracle数据库环境中,可能会遇到一条警告信息:“Heap size 3597K exceeds notification threshold”。这条消息...

    解决Java_heap_space问题

    ### 解决Java_heap_space问题:深入理解与策略 在Java应用程序开发与运行过程中,经常会遇到一个常见的内存管理问题——“Java heap space”。这个问题通常表现为Java虚拟机(JVM)在执行过程中因可用堆内存不足而...

    heapdump分析工作heapanalyzer的使用及工具

    heapdump分析工作heapanalyzer的使用及工具 java -Xmx1000m -jar ha443.jar

    could not reserve enough space for object heap

    "could not reserve enough space for object heap" 是一个常见的Java虚拟机(JVM)启动时遇到的问题,这通常意味着JVM在尝试分配堆内存时遇到了不足的空间。这个问题涉及到Java内存管理和虚拟机配置,对于理解Java...

    基于HeapAnalyzer456.jar 分析java内存溢出

    Java内存分为堆内存(Heap)和非堆内存(Non-Heap),其中堆内存主要存储对象实例,当程序创建过多的对象而无法在堆内存中找到足够的空间时,就会出现内存溢出。非堆内存则包含JVM自身运行所需的内存,如方法区、栈...

    java错误处理:java.lang.OutOfMemoryError: Java heap space

    ### Java 错误处理:java.lang.OutOfMemoryError: Java heap space 在Java应用程序开发过程中,经常遇到的一个问题就是内存溢出错误,特别是在处理大量数据或长时间运行的应用时。其中,“java.lang....

    ibm HeapAnalyzer java内存分析工具 ha457.jar

    IBM HeapAnalyzer是一款强大的Java内存分析工具,主要用于诊断和解决Java应用程序中的内存泄漏问题。这款工具通过对Java堆内存的深入分析,帮助开发者定位那些占用过多内存的对象,从而优化应用性能。在Java开发过程...

    使用IBM性能分析工具HeapAnalyzer解决生产环境中的性能问题

    使用 IBM 性能分析工具 HeapAnalyzer 解决生产环境中的性能问题 性能分析是企业级应用系统软件不可或缺的一部分,对于业务操作的响应时间和并发数的要求非常高。只有经过不断的调整优化,才能达到资源的最大利用率...

Global site tag (gtag.js) - Google Analytics