`

Heap

 
阅读更多

 

/**
 * An implementation of a heap. Elements stored in the heap must implement the
 * Comparable interface.
 * */
public class Heap {
	private Comparable[] heap;
	private int size;
	private int capacity;
	private int capacityIncrement;

	/**
	 * Construct a heap with initial capacity 10 and capacity increment 0
	 * */
	public Heap() {
		this(10, 0);
	}

	/**
	 * Construct a heap with initial capacity c and capacity increment 0
	 * 
	 * @param c initial capacity for heap
	 * @exception IllegalArgumentException c is negative
	 * */
	public Heap(int c) {
		this(c, 0);
	}

	/**
	 * Construct a heap with initial capacity c and capacity increment ci
	 * 
	 * @param c initial capacity for heap
	 * @param ci capacity increment for heap
	 * @exception IllegalArgumentException c or ci is negative
	 * */
	public Heap(int c, int ci) {
		if (c < 0 || ci < 0)
			throw new IllegalArgumentException();
		size = 0;
		capacity = c;
		capacityIncrement = ci;
		heap = new Comparable[capacity + 1];
	}

	/**
	 * Return the size of the heap
	 *
	 * @return the number of elements contained in the heap
	 * */
	public int size() {
		return size;
	}

	/**
	 * Return the capacity of the heap
	 *
	 * @return the size of the internal array used to store the heap
	 * */
	public int capacity() {
		return capacity;
	}

	/**
	 * Insert an element into the heap
	 * 
	 * @param value object to insert
	 * @exception IllegalArgumentException value is null
	 * */
	public void insert(Comparable value) {
		if (value == null)
			throw new IllegalArgumentException();

		if (size == capacity) {
			if (capacityIncrement == 0)
				capacity *= 2;
			else
				capacity += capacityIncrement;

			Comparable[] temp = new Comparable[capacity + 1];
			System.arraycopy(heap, 1, temp, 1, size);
			heap = temp;
		}

		heap[++size] = value; // add at end of array
		siftUp(heap, size, size); // restore heap property
	}

	/**
	 * Remove top element from the heap
	 * 
	 * @return the element with the greatest value from the heap
	 * @exception EmptyHeapException heap is empty
	 * */
	public Comparable remove() throws Exception {
		switch (size) {
		case 0:
			throw new Exception("heap is empty");
		case 1:
			return heap[size--]; // special case for size = 1
		default:
			Comparable ret = heap[1]; // will return top element
			heap[1] = heap[size--]; // move last element at top and adjust size
			siftDown(heap, size, 1); // restore heap property
			return ret;
		}
	}

	/**
	 * Sift an element up to its correct place in the heap
	 * 
	 * @param A array containing the heap
	 * @param size size of heap
	 * @param pos position of element that we sift up
	 * @exception IllegalArgumentException pos < 1 or pos > size or size > A.length
	 **/
	private static void siftUp(Comparable[] A, int size, int pos) {
		if (pos < 1 || pos > size || size > A.length)
			throw new IllegalArgumentException();

		int child = pos;
		int parent = child / 2;
		Comparable value = A[child];

		while (parent > 0) {
			if (A[parent].compareTo(value) < 0) {
				A[child] = A[parent];
				child = parent;
				parent = parent / 2;
			} else
				break;
		}

		A[child] = value;
	}

	/**
	 * Sift an element down to its correct place in the heap
	 * 
	 * @param A array containing the heap
	 * @param size size of heap
	 * @param pos position of element that we sift down
	 * @exception IllegalArgumentException pos < 1 or pos > size or size > A.length
	 */
	private static void siftDown(Comparable[] A, int size, int pos) {
		if (pos < 1 || pos > size || size > A.length)
			throw new IllegalArgumentException();

		int parent = pos;
		int child = 2 * parent;
		Comparable value = A[parent];

		while (child <= size) {
			if (child < size && A[child].compareTo(A[child + 1]) < 0)
				child++;

			if (A[child].compareTo(value) > 0) {
				A[parent] = A[child];
				parent = child;
				child = 2 * child;
			} else
				break;
		}

		A[parent] = value;
	}

	/**
	 * Transform an array into a heap
	 * 
	 * @param A array that we want to transform into a heap
	 * @param size number of elements
	 * @exception IllegalArgumentException size > A.length
	 **/
	private static void heapify(Comparable[] A, int size) {
		if (size > A.length)
			throw new IllegalArgumentException();

		for (int i = size / 2; i > 0; i--)
			siftDown(A, size, i);
	}
}

 

Reference:

http://www.cs.umb.edu/~dana/GAClust/src/Heap.java 

分享到:
评论

相关推荐

    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