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.