Package org.onlab.graph

Class Heap<T>

  • Type Parameters:
    T - type of the items on the heap
    public class Heap<T>
extends java.lang.Object
    Implementation of an array-backed heap structure whose sense of order is imposed by the provided comparator.

    While this provides similar functionality to PriorityQueue data structure, one key difference is that external entities can control when to restore the heap property, which is done through invocation of the heapify() method.

    This class is not thread-safe and care must be taken to prevent concurrent modifications.

    • Constructor Summary

      Constructors 
      Constructor Description
      Heap​(java.util.List<T> data, java.util.Comparator<T> comparator)
      Creates a new heap backed by the specified list.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean equals​(java.lang.Object obj)  
      T extractExtreme()
      Extracts and returns the most extreme item from the heap.
      T extreme()
      Returns the most extreme item in the heap.
      int hashCode()  
      void heapify()
      Restores the heap property by re-arranging the elements in the backing array as necessary following any heap modifications.
      Heap<T> insert​(T item)
      Inserts the specified item into the heap and returns the modified heap.
      boolean isEmpty()
      Returns true if there are no items in the heap.
      java.util.Iterator<T> iterator()
      Returns iterator to traverse the heap level-by-level.
      int size()
      Returns the current size of the heap.
      java.lang.String toString()  

      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait

    • Constructor Detail

      • Heap

        public Heap​(java.util.List<T> data,
            java.util.Comparator<T> comparator)
        Creates a new heap backed by the specified list. In the interest of efficiency, the list should be array-backed. Also, for the same reason, the data is not copied and therefore, the caller must assure that the backing data is not altered in any way.
        Parameters:
        data - backing data list
        comparator - comparator for ordering the heap items

    • Method Detail

      • heapify

        public void heapify()
        Restores the heap property by re-arranging the elements in the backing array as necessary following any heap modifications.

      • size

        public int size()
        Returns the current size of the heap.
        Returns:
        number of items in the heap

      • isEmpty

        public boolean isEmpty()
        Returns true if there are no items in the heap.
        Returns:
        true if heap is empty

      • extreme

        public T extreme()
        Returns the most extreme item in the heap.
        Returns:
        heap extreme or null if the heap is empty

      • extractExtreme

        public T extractExtreme()
        Extracts and returns the most extreme item from the heap.
        Returns:
        heap extreme or null if the heap is empty

      • insert

        public Heap<T> insert​(T item)
        Inserts the specified item into the heap and returns the modified heap.
        Parameters:
        item - item to be inserted
        Returns:
        the heap self
        Throws:
        java.lang.IllegalArgumentException - if the heap is already full

      • iterator

        public java.util.Iterator<T> iterator()
        Returns iterator to traverse the heap level-by-level. This iterator does not permit removal of items.
        Returns:
        non-destructive heap iterator

      • equals

        public boolean equals​(java.lang.Object obj)
        Overrides:
        equals in class java.lang.Object

      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object