Below is the syntax highlighted version of IndexBinomialMinPQ.java
from §9.9 Miscellaneous.
/****************************************************************************** * Compilation: javac IndexBinomialMinPQ.java * Execution: * * An index binomial heap. * ******************************************************************************/ import java.util.Comparator; import java.util.Iterator; import java.util.NoSuchElementException; /** * The IndexBinomialMinPQ class represents an indexed priority queue of generic keys. * It supports the usual insert and delete-the-minimum operations, * along with delete and change-the-key methods. * In order to let the client refer to keys on the priority queue, * an integer between 0 and N-1 is associated with each key ; the client * uses this integer to specify which key to delete or change. * It also supports methods for peeking at the minimum key, * testing if the priority queue is empty, and iterating through * the keys. * * This implementation uses a binomial heap along with an array to associate * keys with integers in the given range. * The insert, delete-the-minimum, delete, change-key, decrease-key, * increase-key and size operations take logarithmic time. * The is-empty, min-index, min-key, and key-of operations take constant time. * Construction takes time proportional to the specified capacity. * * @author Tristan Claverie */ public class IndexBinomialMinPQ<Key> implements Iterable<Integer> { private Node<Key> head; //Head of the list of roots private Node<Key>[] nodes; //Array of indexed Nodes of the heap private int n; //Maximum size of the tree private final Comparator<Key> comparator; //Comparator over the keys //Represents a node of a Binomial Tree private class Node<Key> { Key key; //Key contained by the Node int order; //The order of the Binomial Tree rooted by this Node int index; //Index associated with the Key Node<Key> parent; //parent of this Node Node<Key> child, sibling; //child and sibling of this Node } /** * Initializes an empty indexed priority queue with indices between {@code 0} to {@code N-1} * Worst case is O(n) * @param N number of keys in the priority queue, index from {@code 0} to {@code N-1} * @throws java.lang.IllegalArgumentException if {@code N < 0} */ public IndexBinomialMinPQ(int N) { if (N < 0) throw new IllegalArgumentException("Cannot create a priority queue of negative size"); comparator = new MyComparator(); nodes = (Node<Key>[]) new Node[N]; this.n = N; } /** * Initializes an empty indexed priority queue with indices between {@code 0} to {@code N-1} * Worst case is O(n) * @param N number of keys in the priority queue, index from {@code 0} to {@code N-1} * @param comparator a Comparator over the keys * @throws java.lang.IllegalArgumentException if {@code N < 0} */ public IndexBinomialMinPQ(int N, Comparator<Key> comparator) { if (N < 0) throw new IllegalArgumentException("Cannot create a priority queue of negative size"); this.comparator = comparator; nodes = (Node<Key>[]) new Node[N]; this.n = N; } /** * Whether the priority queue is empty * Worst case is O(1) * @return true if the priority queue is empty, false if not */ public boolean isEmpty() { return head == null; } /** * Does the priority queue contains the index i ? * Worst case is O(1) * @param i an index * @throws java.lang.IllegalArgumentException if the specified index is invalid * @return true if i is on the priority queue, false if not */ public boolean contains(int i) { if (i < 0 || i >= n) throw new IllegalArgumentException(); else return nodes[i] != null; } /** * Number of elements currently on the priority queue * Worst case is O(log(n)) * @return the number of elements on the priority queue */ public int size() { int result = 0, tmp; for (Node<Key> node = head; node != null; node = node.sibling) { if (node.order > 30) { throw new ArithmeticException("The number of elements cannot be evaluated, but the priority queue is still valid."); } tmp = 1 << node.order; result |= tmp; } return result; } /** * Associates a key with an index * Worst case is O(log(n)) * @param i an index * @param key a Key associated with i * @throws java.lang.IllegalArgumentException if the specified index is invalid * @throws java.lang.IllegalArgumentException if the index is already in the queue */ public void insert(int i, Key key) { if (i < 0 || i >= n) throw new IllegalArgumentException(); if (contains(i)) throw new IllegalArgumentException("Specified index is already in the queue"); Node<Key> x = new Node<Key>(); x.key = key; x.index = i; x.order = 0; nodes[i] = x; IndexBinomialMinPQ<Key> H = new IndexBinomialMinPQ<Key>(); H.head = x; head = union(H).head; } /** * Gets the index associated with the minimum key * Worst case is O(log(n)) * @throws java.util.NoSuchElementException if the priority queue is empty * @return the index associated with the minimum key */ public int minIndex() { if (isEmpty()) throw new NoSuchElementException("Priority queue is empty"); Node<Key> min = head; Node<Key> current = head; while (current.sibling != null) { min = (greater(min.key, current.sibling.key)) ? current.sibling : min; current = current.sibling; } return min.index; } /** * Gets the minimum key currently in the queue * Worst case is O(log(n)) * @throws java.util.NoSuchElementException if the priority queue is empty * @return the minimum key currently in the priority queue */ public Key minKey() { if (isEmpty()) throw new NoSuchElementException("Priority queue is empty"); Node<Key> min = head; Node<Key> current = head; while (current.sibling != null) { min = (greater(min.key, current.sibling.key)) ? current.sibling : min; current = current.sibling; } return min.key; } /** * Deletes the minimum key * Worst case is O(log(n)) * @throws java.util.NoSuchElementException if the priority queue is empty * @return the index associated with the minimum key */ public int delMin() { if(isEmpty()) throw new NoSuchElementException("Priority queue is empty"); Node<Key> min = eraseMin(); Node<Key> x = (min.child == null) ? min : min.child; if (min.child != null) { min.child = null; Node<Key> prevx = null, nextx = x.sibling; while (nextx != null) { x.parent = null; // for garbage collection x.sibling = prevx; prevx = x; x = nextx;nextx = nextx.sibling; } x.parent = null; x.sibling = prevx; IndexBinomialMinPQ<Key> H = new IndexBinomialMinPQ<Key>(); H.head = x; head = union(H).head; } return min.index; } /** * Gets the key associated with index i * Worst case is O(1) * @param i an index * @throws java.lang.IllegalArgumentException if the specified index is invalid * @throws java.lang.IllegalArgumentException if the index is not in the queue * @return the key associated with index i */ public Key keyOf(int i) { if (i < 0 || i >= n) throw new IllegalArgumentException(); if (!contains(i)) throw new IllegalArgumentException("Specified index is not in the queue"); return nodes[i].key; } /** * Changes the key associated with index i to the given key * Worst case is O(log(n)) * @param i an index * @param key the key to associate with i * @throws java.lang.IllegalArgumentException if the specified index is invalid * @throws java.lang.IllegalArgumentException if the index has no key associated with */ public void changeKey(int i, Key key) { if (i < 0 || i >= n) throw new IllegalArgumentException(); if (!contains(i)) throw new IllegalArgumentException("Specified index is not in the queue"); if (greater(nodes[i].key, key)) decreaseKey(i, key); else increaseKey(i, key); } /** * Decreases the key associated with index i to the given key * Worst case is O(log(n)) * @param i an index * @param key the key to associate with i * @throws java.lang.IllegalArgumentException if the specified index is invalid * @throws java.util.NoSuchElementException if the index has no key associated with * @throws java.lang.IllegalArgumentException if the given key is greater than the current key */ public void decreaseKey(int i, Key key) { if (i < 0 || i >= n) throw new IllegalArgumentException(); if (!contains(i)) throw new NoSuchElementException("Specified index is not in the queue"); if (greater(key, nodes[i].key)) throw new IllegalArgumentException("Calling with this argument would not decrease the key"); Node<Key> x = nodes[i]; x.key = key; swim(i); } /** * Increases the key associated with index i to the given key * Worst case is O(log(n)) * @param i an index * @param key the key to associate with i * @throws java.lang.IllegalArgumentException if the specified index is invalid * @throws java.util.NoSuchElementException if the index has no key associated with * @throws java.lang.IllegalArgumentException if the given key is lower than the current key */ public void increaseKey(int i, Key key) { if (i < 0 || i >= n) throw new IllegalArgumentException(); if (!contains(i)) throw new NoSuchElementException("Specified index is not in the queue"); if (greater(nodes[i].key, key)) throw new IllegalArgumentException("Calling with this argument would not increase the key"); delete(i); insert(i, key); } /** * Deletes the key associated the given index * Worst case is O(log(n)) * @param i an index * @throws java.lang.IllegalArgumentException if the specified index is invalid * @throws java.util.NoSuchElementException if the given index has no key associated with */ public void delete(int i) { if (i < 0 || i >= n) throw new IllegalArgumentException(); if (!contains(i)) throw new NoSuchElementException("Specified index is not in the queue"); toTheRoot(i); Node<Key> x = erase(i); if (x.child != null) { Node<Key> y = x; x = x.child; y.child = null; Node<Key> prevx = null, nextx = x.sibling; while (nextx != null) { x.parent = null; x.sibling = prevx; prevx = x; x = nextx; nextx = nextx.sibling; } x.parent = null; x.sibling = prevx; IndexBinomialMinPQ<Key> H = new IndexBinomialMinPQ<Key>(); H.head = x; head = union(H).head; } } /************************************************* * General helper functions ************************************************/ //Compares two keys private boolean greater(Key n, Key m) { if (n == null) return false; if (m == null) return true; return comparator.compare(n, m) > 0; } //Exchanges the positions of two nodes private void exchange(Node<Key> x, Node<Key> y) { Key tempKey = x.key; x.key = y.key; y.key = tempKey; int tempInt = x.index; x.index = y.index; y.index = tempInt; nodes[x.index] = x; nodes[y.index] = y; } //Assuming root1 holds a greater key than root2, root2 becomes the new root private void link(Node<Key> root1, Node<Key> root2) { root1.sibling = root2.child; root1.parent = root2; root2.child = root1; root2.order++; } /************************************************* * Functions for moving upward ************************************************/ //Moves a Node upward private void swim(int i) { Node<Key> x = nodes[i]; Node<Key> parent = x.parent; if (parent != null && greater(parent.key, x.key)) { exchange(x, parent); swim(i); } } //The key associated with i becomes the root of its Binomial Tree, //regardless of the order relation defined for the keys private void toTheRoot(int i) { Node<Key> x = nodes[i]; Node<Key> parent = x.parent; if (parent != null) { exchange(x, parent); toTheRoot(i); } } /************************************************** * Functions for deleting a key *************************************************/ //Assuming the key associated with i is in the root list, //deletes and return the node of index i private Node<Key> erase(int i) { Node<Key> reference = nodes[i]; Node<Key> x = head; Node<Key> previous = null; while (x != reference) { previous = x; x = x.sibling; } previous.sibling = x.sibling; if (x == head) head = head.sibling; nodes[i] = null; return x; } //Deletes and return the node containing the minimum key private Node<Key> eraseMin() { Node<Key> min = head; Node<Key> previous = null; Node<Key> current = head; while (current.sibling != null) { if (greater(min.key, current.sibling.key)) { previous = current; min = current.sibling; } current = current.sibling; } previous.sibling = min.sibling; if (min == head) head = min.sibling; nodes[min.index] = null; return min; } /************************************************** * Functions for inserting a key in the heap *************************************************/ //Merges two root lists into one, there can be up to 2 Binomial Trees of same order private Node<Key> merge(Node<Key> h, Node<Key> x, Node<Key> y) { if (x == null && y == null) return h; else if (x == null) h.sibling = merge(y, null, y.sibling); else if (y == null) h.sibling = merge(x, x.sibling, null); else if (x.order < y.order) h.sibling = merge(x, x.sibling, y); else h.sibling = merge(y, x, y.sibling); return h; } //Merges two Binomial Heaps together and returns the resulting Binomial Heap //It destroys the two Heaps in parameter, which should not be used any after. //To guarantee logarithmic time, this function assumes the arrays are up-to-date private IndexBinomialMinPQ<Key> union(IndexBinomialMinPQ<Key> heap) { this.head = merge(new Node<Key>(), this.head, heap.head).sibling; Node<Key> x = this.head; Node<Key> prevx = null, nextx = x.sibling; while (nextx != null) { if (x.order < nextx.order || (nextx.sibling != null && nextx.sibling.order == x.order)) { prevx = x; x = nextx; } else if (greater(nextx.key, x.key)) { x.sibling = nextx.sibling; link(nextx, x); } else { if (prevx == null) { this.head = nextx; } else { prevx.sibling = nextx; } link(x, nextx); x = nextx; } nextx = x.sibling; } return this; } /****************************************************************** * Constructor *****************************************************************/ //Creates an empty heap //The comparator is instanciated because it needs to, //but won't be used by any heap created by this constructor private IndexBinomialMinPQ() { comparator = null; } /****************************************************************** * Iterator *****************************************************************/ /** * Gets an Iterator over the indexes in the priority queue in ascending order * The Iterator does not implement the remove() method * iterator() : Worst case is O(n) * next() : Worst case is O(log(n)) * hasNext() : Worst case is O(1) * @return an Iterator over the indexes in the priority queue in ascending order */ public Iterator<Integer> iterator() { return new MyIterator(); } private class MyIterator implements Iterator<Integer> { IndexBinomialMinPQ<Key> data; //Constructor clones recursively the elements in the queue //It takes linear time public MyIterator() { data = new IndexBinomialMinPQ<Key>(n, comparator); data.head = clone(head, null); } private Node<Key> clone(Node<Key> x, Node<Key> parent) { if (x == null) return null; Node<Key> node = new Node<Key>(); node.index = x.index; node.key = x.key; data.nodes[node.index] = node; node.parent = parent; node.sibling = clone(x.sibling, parent); node.child = clone(x.child, node); return node; } public boolean hasNext() { return !data.isEmpty(); } public Integer next() { if (!hasNext()) throw new NoSuchElementException(); return data.delMin(); } public void remove() { throw new UnsupportedOperationException(); } } /*************************** * Comparator **************************/ //default Comparator private class MyComparator implements Comparator<Key> { @Override public int compare(Key key1, Key key2) { return ((Comparable<Key>) key1).compareTo(key2); } } }