Package org.jboss.util

Class Heap

  • public class Heap
extends java.lang.Object
    Data structure that mantains data in a ordered binary tree; each node is greater (smaller) or equal than its 2 sub-nodes, for all the hierarchy.

    Elements of this data structure should either implement Comparable, or a Comparator should be given as argument to the constructor.

    Version:
    $Revision$

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.Comparator m_comparator  
      private int m_count  
      private java.lang.Object[] m_nodes  

    • Constructor Summary

      Constructors 
      Constructor Description
      Heap()
      Creates a new Heap whose elements inserted implement the Comparable interface.
      Heap​(java.util.Comparator comparator)
      Creates a new Heap whose elements are compared using the given Comparator.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()
      Empties this heap
      protected int compare​(java.lang.Object o1, java.lang.Object o2)  
      java.lang.Object extract()
      Removes and returns the least element of this heap.
      void insert​(java.lang.Object obj)
      Inserts the given element in this heap.
      protected int left​(int index)  
      protected int parent​(int index)  
      java.lang.Object peek()  
      protected int right​(int index)  

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • m_comparator

        private java.util.Comparator m_comparator

      • m_count

        private int m_count

      • m_nodes

        private java.lang.Object[] m_nodes

    • Constructor Detail

      • Heap

        public Heap()
        Creates a new Heap whose elements inserted implement the Comparable interface.

      • Heap

        public Heap​(java.util.Comparator comparator)
        Creates a new Heap whose elements are compared using the given Comparator.
        Parameters:
        comparator -

    • Method Detail

      • insert

        public void insert​(java.lang.Object obj)
        Inserts the given element in this heap.
        Parameters:
        obj -
        See Also:
        extract()

      • extract

        public java.lang.Object extract()
        Removes and returns the least element of this heap.
        Returns:
        the extracted object
        See Also:
        insert(java.lang.Object), peek()

      • peek

        public java.lang.Object peek()
        Returns:
        without removing it, the least element of this heap.
        See Also:
        extract()

      • clear

        public void clear()
        Empties this heap

      • compare

        protected int compare​(java.lang.Object o1,
                      java.lang.Object o2)

      • parent

        protected int parent​(int index)
        Parameters:
        index -
        Returns:
        the parent index of index.

      • left

        protected int left​(int index)
        Parameters:
        index -
        Returns:
        the left child index of index.

      • right

        protected int right​(int index)
        Parameters:
        index -
        Returns:
        the right child index of index.