Package org.onlab.graph

Class Heap<T>

  • Type Parameters:
    T - type of the items on the heap
    public class Heap<T>
extends 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 Detail

      • Heap

        public Heap​(List<T> data,
            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:
        IllegalArgumentException - if the heap is already full

      • iterator

        public 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

      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class Object