Notes

Heap

The concept behind the heap is to balance the tradeoffs of the unsorted and the sorted priority queue. Rather than having to choose O(1) add and O(N) removal, or O(N) add and O(1) removal, the heap allows O(log N) insertion and removal both.

The heap order is defined as follows:

Root node must be the smallest key value
Child nodes must have greater key values than parent nodes

Heaps T must have minimal height

Heap T must be complete

Left and right subtrees cannot differ by more than 1 hierarchical level
Packing in the heap tree from left to right, top to bottom
Height = floor(log(N))

Heap Add

Add to the next spot in the tree

We pack in the heap tree from left to right, top to bottom
We insert new nodes at the very bottom of the tree, last row, filling to the right.
After we insert a new node, the heap tree may violate heap order property (HOP)
Heap post-add procedure: up-heap bubbling

if the position of the new node is not root:
    compare p to p's parent q
    if k_p < k_q:
        swap p and q
        re-apply up-heap bubbling to parent

Heap Remove

Remove root of the tree (minimum item in tree)

Minimum item is always at root, so removing it is always an O(1) operation
Rearranging tree after that to preserve heap order property is not an O(1) operation, it's an O(log N) operation
Root node is removed, replaced with last node in tree (right-most node of last layer)
Heap post-remove procedure: down-heap bubbling

if T has one node (root), we are done
if one child, let c be child of p
if two children, let c be smaller of p's children
if k_p > k_c, swap to restore heap order property and continue to apply down tree

Organization

To implement a priority queue using a heap, and utilizing good object-oriented principles:

Utilize a priority queue abstract data type like Priority Queues/ADT to provide a standard interface
The heap data structure is utilized entirely under the hood, and is implemented as an array or a linked structure or whatever
Following the design of the abstract priority queue type, the heap-based priority queue defines an empty default constructor, and a constructor that takes a Comparator object (useful for defining how to compare keys)
The priority queue implementation should have a method of getting the neighbors of a node, given a particular node location. This might be using a Location object, or an integer (index in array). For an array-based heap, this can take an index argument.

For interfacing with the heap:

The post-add and post-remove up-heap and down-heap bubble methods should be private utility methods
swap method for swapping nodes in heap also useful

Public methods required by interface:

insert
removeMin
peekMin
size
iterator

Code

The final heap class takes a key and value type pair. See link for latest.

Link: https://git.charlesreid1.com/cs/java/src/master/priority-queues/HeapPQ.java

public class HeapPQ<K,V> extends AbstractPriorityQueue<K,V> { 

	protected ArrayList<Item<K,V>> heap;

	// cmr: constructor calls super first. then makes list.
	public HeapPQ() { 
		super();
		heap = new ArrayList<Item<K,V>>();
	}

	// cmr: remember this was how we designed our abstract priority queue,
	// so that all PQ classes could use comparators and compare things however they want.
	public HeapPQ(Comparator<K> keyComparator) { 
		super(keyComparator);
	}

	// this is always useful to do right after the constructors
	public String toString() { 
		return heap.toString();
	}

	public void clear() { 
		heap.clear();
	}

	// cmr: index math to turn a node into its parent/left/right nodes
	protected int parent(int j) { return (j-1)/2; }
	protected int left(int j) { return 2*j + 1; } 
	protected int right(int j) { return 2*j + 2; }

	// cmr: boolean checks if left/right exist in the heap 
	protected boolean hasLeft(int j) { return left(j) < heap.size(); }
	protected boolean hasRight(int j) { return right(j) < heap.size(); }




	// Utility:

	// swap
	protected void swap(int i, int j) {
		Item<K,V> temp = heap.get(i);
		heap.set(i, heap.get(j));
		heap.set(j, temp);
	}

	// upheap
	protected void upheap(int j) { 
		// j==0 is root
		while(j>0) { 
			int p = parent(j);
			if(compare(heap.get(j), heap.get(p))>=0) {
				break; // heap order property satisfied
			}
			swap(j,p);
			j = p; // continue from parent
		}
	}

	// recursive upheap
	protected void upheap_r(int j) { 
		// now check for recursive case
		int p = parent(j);
		if(compare(heap.get(j), heap.get(p))<0) {
			swap(j,p);
			upheap_r(p);
		}
		// else base case, return nothing
	}


	// downheap
	protected void downheap(int j) { 
		while(hasLeft((j))) {
			int leftIndex = left(j);
			// assume left child is smaller
			int smallChildIndex = leftIndex;
			// if right child exists, check if right child is smaller
			if(hasRight(j)) { 
				int rightIndex = right(j);
				if(compare(heap.get(leftIndex), heap.get(rightIndex))>0) {
					smallChildIndex = rightIndex;
				}
			}
			if(compare(heap.get(smallChildIndex), heap.get(j)) >= 0) { 
				break; // heap order property satisfied
			}
			swap(j, smallChildIndex);
			j = smallChildIndex; // continue from child
		}
	}

	// recursive downheap
	protected void downheap_r(int j) { 
		if(hasLeft(j)) { 
			int leftIndex = left(j);
			// assume left child is smaller
			int smallChildIndex = leftIndex;
			// if right child exists, check if right child is smaller
			if(hasRight(j)) { 
				int rightIndex = right(j);
				if(compare(heap.get(leftIndex), heap.get(rightIndex))>0) {
					smallChildIndex = rightIndex;
				}
			}
			// now check for recursive case
			if(compare(heap.get(smallChildIndex), heap.get(j))<0) { 
				swap(j, smallChildIndex);
				downheap_r(smallChildIndex);
			}
			// else base case, return nothing
		}
	}





	// Really, the main content of this class
	// (other than the upheap/downheap/swap methods):

	// insert
	public void insert(K key, V value) { 
		checkKey(key);
		Item<K,V> newitem = new Item<K,V>(key, value);
		heap.add(newitem);
		upheap( heap.size() - 1 ); // upheap the newest entry (last item in array)
	}

	// remove min
	public V removeMin() { 
		if(heap.isEmpty()) { 
			throw new Empty();
		}
		// before you lose the reference to the minimum item,
		// get a reference to it.
		Item<K,V> expunge = heap.get(0);
		// swap the minimum item with the item that will replace it 
		swap(0, heap.size()-1); // swap the base of the heap with the last item in the tree
		heap.remove(heap.size()-1); // remove the last item, which no one cares about anymore
		downheap(0); // restore heap order priority (HOP)
		return expunge.getValue(); // return the value of the item we grabbed before removing.
	}

	public V peekMin() {
		if(heap.isEmpty()) { 
			throw new Empty();
		}
		return heap.get(0).getValue();
	}


	// No KLE implementation here,
	// because that requires location,
	// and that requires this adaptable priority queue,
	// and that requires using Goodrich's 
	// confusing Locator wrapper class,
	// more nonsense.


	// Priority queue interface:

	// get size
	public int size() { 
		return heap.size();
	}

	// protected iterator class for making this class iterable (PriorityQueue extends Iterable)
	protected class ItemIterator implements Iterator<K> {
		Iterator<Item<K,V>> it;
		public ItemIterator() { 
			it = heap.iterator();
		}
		public boolean hasNext() { return it.hasNext(); }
		public K next() { return it.next().getKey(); }
		public void remove() { it.remove(); }
	}

	public Iterator<K> iterator() { 
		return new ItemIterator();
	}
}

Flag

Priority Queues/Heap

From charlesreid1

Contents