Package net.cscott.jutil

Class BinomialHeap<K,V>

java.lang.Object
net.cscott.jutil.AbstractHeap<K,V>
net.cscott.jutil.BinomialHeap<K,V>
All Implemented Interfaces:
Cloneable, Iterable<Map.Entry<K,V>>, Heap<K,V>
public class BinomialHeap<K,V> extends AbstractHeap<K,V> implements Cloneable
A BinomialHeap allows O(lg n) time bounds for insert, minimum, extract-min, union, decrease-key, and delete operations. Implementation is based on the description in Introduction to Algorithms by Cormen, Leiserson, and Rivest, on page 400 and following.
Author:
C. Scott Ananian <cananian@alumni.princeton.edu>

  • Constructor Details

    • BinomialHeap

      public BinomialHeap()
      Constructs a new, empty BinomialHeap, sorted according to the keys' natural order. All keys inserted into the new map must implement the Comparable interface. O(1) time.

    • BinomialHeap

      public BinomialHeap(Comparator<? super K> c)
      Constructs a new, empty BinomialHeap, sorted according to the given comparator. O(1) time.

    • BinomialHeap

      public BinomialHeap(Heap<K,? extends V> h)
      Constructs a new binomial heap with the same entries as the specified Heap. O(n) time.

    • BinomialHeap

      public BinomialHeap(Collection<? extends Map.Entry<? extends K,? extends V>> collection, Comparator<? super K> comparator)
      Constructs a binomial heap from a collection of Map.Entrys and a key comparator. O(n) time.

  • Method Details

    • minimum

      public Map.Entry<K,V> minimum()
      Returns a mapping entry with minimal key. Takes O(lg n) time.
      Specified by:
      minimum in interface Heap<K,V>
      Specified by:
      minimum in class AbstractHeap<K,V>

    • union

      public void union(Heap<? extends K,? extends V> h)
      Add all the entries from the given heap to this one. The given heap will be empty on return. Takes O(lg n) time if the given heap is a BinomialHeap and its entry comparator is the same as this one's. Otherwise, it takes O(n) time.
      Specified by:
      union in interface Heap<K,V>
      Overrides:
      union in class AbstractHeap<K,V>

    • union

      public void union(BinomialHeap<K,V> m)
      Merges all of the mappings from the specified map to this map. Note that duplicates are permitted. This operation takes O(lg n), where n is the number of entries in the resulting map. The comparator for m must be identical to the comparator for this. After calling union(), the specified map will be empty.

    • insert

      public Map.Entry<K,V> insert(K key, V value)
      Associates the specified value with the specified key in the map. If the map previously contained a mapping for this key, the old value is not replaced; both mappings will be present after the insert(). O(lg n) time.
      Specified by:
      insert in interface Heap<K,V>
      Specified by:
      insert in class AbstractHeap<K,V>
      Returns:
      The Map.Entry added.

    • insert

      protected void insert(Map.Entry<K,V> me)
      Description copied from class: AbstractHeap
      This method should insert the specified Map.Entry, which is not currently in the Heap, into the Heap. Implementation is optional, but it is required if you use the default implementation of updateKey().
      Overrides:
      insert in class AbstractHeap<K,V>

    • extractMinimum

      public Map.Entry<K,V> extractMinimum()
      Remove and return the map entry with minimal key. O(lg n) time.
      Specified by:
      extractMinimum in interface Heap<K,V>
      Overrides:
      extractMinimum in class AbstractHeap<K,V>

    • decreaseKey

      public void decreaseKey(Map.Entry<K,V> me, K newkey)
      Replace the key in the specified map entry with the specified smaller key. O(lg n) time.
      Specified by:
      decreaseKey in interface Heap<K,V>
      Specified by:
      decreaseKey in class AbstractHeap<K,V>

    • delete

      public void delete(Map.Entry<K,V> me)
      Remove the specified map entry from the mapping. O(lg n) time.
      Specified by:
      delete in interface Heap<K,V>
      Specified by:
      delete in class AbstractHeap<K,V>

    • entries

      public Collection<Map.Entry<K,V>> entries()
      Return an unmodifiable collection of entries in this heap.
      Specified by:
      entries in interface Heap<K,V>
      Specified by:
      entries in class AbstractHeap<K,V>

    • size

      public int size()
      Returns the size of this map. O(lg n) time.
      Specified by:
      size in interface Heap<K,V>
      Specified by:
      size in class AbstractHeap<K,V>

    • clear

      public void clear()
      Removes all mappings from this map. O(1) time.
      Specified by:
      clear in interface Heap<K,V>
      Specified by:
      clear in class AbstractHeap<K,V>

    • isEmpty

      public boolean isEmpty()
      Returns true if this map contains no key-value mappings.
      Specified by:
      isEmpty in interface Heap<K,V>
      Overrides:
      isEmpty in class AbstractHeap<K,V>

    • clone

      public BinomialHeap<K,V> clone()
      Creates a new BinomialHeap with all the key-value pairs this one has. O(n) time.
      Overrides:
      clone in class Object

    • find

      public Map.Entry<K,V> find(K key)
      Lookup a Map.Entry in the heap with key equal to the specified key. O(n), although pruning is done on subtrees with root larger than the specified key. What this means is that the smaller the key is, the faster this will run.

    • setKey

      protected final K setKey(Map.Entry<K,V> me, K newkey)
      Description copied from class: AbstractHeap
      This method should set the key for the specified Map.Entry to the given newkey. Implementation is optional, but it is required if you use the default implementation of updateKey().
      Overrides:
      setKey in class AbstractHeap<K,V>