Heaps

Why are priority queues helpful?

Different people get priority in certain cases:

• scheduling

• boarding a place

• emergency room

Interface

• public void enqueue( E element ) adds the element to this queue

• public E dequeue() removes and returns the element with highest priority

• public E front() returns (but does not remove) the element with the highest priority

Represented by T

• Either T has a natural ordering (e.g., it implements Comparable<T> in Java)

• Or T has a field K (called key) that represents the priority (e.g., an Integer)

• or a Comparator<T> is provided to the constructor of the priority queue.

Priorities as methods

enqueue(element, priority)

• highest priority represented by highest/smaller number

• names of methods differ

  • public void add (E element)

Priority Queue Interface: Comapreator <T>

public interface PriorityQueue<T> {

void add(T item);

T peek();

T remove();

boolean isEmpty();

int size();

}

Priority Queue Interface: priorities explictely provided as part of method calls

public interface PriorityQueue<K extends Comparable<? super K>, V> {

interface Entry<K, V> {

K getKey();

V getValue();

}

int size();

boolean isEmpty();

Entry<K, V> insert(K key, V value);

Entry<K, V> min();

Entry<K, V> removeMin();