Package net.cscott.jutil

Interface Heap<K,V>

All Superinterfaces:
Iterable<Map.Entry<K,V>>
All Known Implementing Classes:
AbstractHeap, BinaryHeap, BinomialHeap, FibonacciHeap
public interface Heap<K,V> extends Iterable<Map.Entry<K,V>>
Heaps support create, insert, minimum, extract-min, union, decrease-key, and delete operations. There are three primary implementations, each with different expected run-times:
Running times for operations on three implementations of mergable heaps. The number of items in the heap(s) at the time of an operation is denoted by n. (From Introduction to Algorithms by Cormen, Leiserson, and Rivest.)
Procedure BinaryHeap
(worst-case)		 BinomialHeap
(worst-case)		 FibonacciHeap
(amortized)
Make-Heap Θ(1) Θ(1) Θ(1)
Insert Θ(lg n) O(lg n) Θ(1)
Minimum Θ(1) O(lg n) Θ(1)
Extract-Min Θ(lg n) Θ(lg n) O(lg n)
Union Θ(n) O(lg n) Θ(1)
Decrease-Key Θ(lg n) Θ(lg n) Θ(1)
Update-Key Θ(lg n) Θ(lg n) Θ(lg n)
Delete Θ(lg n) Θ(lg n) O(lg n)

All implementations of Heap should have a no-argument constructor which implements the Make-Heap operation in the above-stated time bound. In addition, certain implementations may also have constructors which take a Map or Heap and construct a heap in less time than it would take to call insert() on each item on an initially-empty Heap. Note that the Update-Key operation is typically implemented as a delete followed by an insert, which often has worse performance than a Decrease-Key operation. However, some algorithms need to increase keys as well as decrease them; there's nothing you can do about that.

Author:
C. Scott Ananian <cananian@alumni.princeton.edu>
See Also:

  • Method Details

    • insert

      Map.Entry<K,V> insert(K key, V value)
      Inserts a node with the specified key and value into the Heap. Returns the generated Map.Entry which may be stored and eventually passed back to decreaseKey() or delete to remove this node.

    • minimum

      Map.Entry<K,V> minimum()
      Returns a mapping entry with minimal key.
      Throws:
      NoSuchElementException - if the heap has no entries.

    • extractMinimum

      Map.Entry<K,V> extractMinimum()
      Remove and return a map entry with minimal key.
      Throws:
      NoSuchElementException - if the heap has no entries.

    • union

      void union(Heap<? extends K,? extends V> h)
      Merges all of the mappings from the specified Heap into this Heap. Note that duplicates are permitted. After calling union(), the Heap passed in as an argument will be empty.

      Note that usually efficient implementations of this method require that the Heap argument be from the same implementation as this. (That is, they must both be binomial heaps, or both fibonacci heaps, etc.)

    • decreaseKey

      void decreaseKey(Map.Entry<K,V> me, K newkey)
      Replace the key in the specified map entry with the specified smaller key.

    • updateKey

      void updateKey(Map.Entry<K,V> me, K newkey)
      Replace the key in the specified map entry with the specified key, which may be either larger or smaller than its current key.

    • delete

      void delete(Map.Entry<K,V> me)
      Remove the specified map entry from the mapping.

    • isEmpty

      boolean isEmpty()
      Returns true if this Heap has no more entries.

    • clear

      void clear()
      Removes all entries from this Heap.

    • size

      int size()
      Returns the number of entries in this Heap.

    • entries

      Collection<Map.Entry<K,V>> entries()
      Returns a collection view of all the Map.Entrys in this Heap.

    • iterator

      default Iterator<Map.Entry<K,V>> iterator()
      Returns an iterator over the Map.Entrys in this Heap, in no particular order: the iterator of entries().
      Specified by:
      iterator in interface Iterable<K>
      Since:
      2.0

    • hashCode

      int hashCode()
      Returns the hash code for this heap: one greater than the sum of the hash codes of its entries.
      Overrides:
      hashCode in class Object

    • equals

      boolean equals(Object o)
      Compares the specified object with this heap for equality. Returns true iff the given object is also a Heap with the same entries, in any order: each key-value pair is in both heaps the same number of times. The heaps' comparators are not compared.
      Overrides:
      equals in class Object

    • toString

      String toString()
      Returns a string representation of this Heap.
      Overrides:
      toString in class Object

    • comparator

      Comparator<? super K> comparator()
      Returns the comparator associated with this Heap, or null if it uses its elements' natural ordering.