Priority Queues & Heaps Flashcards
What is a priority queue ADT and how does it work?
Stores a collection of entries. Each entry is a (key, value) pair
What are total order relations?
Keys in a priority queue can be arbitrary objects on which an order is defined between all different pairs.
A mathematical concept of a total order relation is (<=)
What is a comparator?
A comparator encapsulates the action of comparing two objects according to a given total order relation.
In summary, it compares two keys and then orders them based on the total order relation pre-specified.
What are the time complexities for insertion and removal of minimum in a sorted and unsorted list (priority queues)?
Unsorted list:
Insertion - O(1)
Removal of minimum - O(n)
Sorted list:
Insertion - O(n)
Removal of minimum - O(1)
What is a heap?
A heap is a binary tree storing key-value pairs at its nodes and satisfying the following properties:
Heap-order - for every internal node v other than the root, key(v) >= key(parent(v))
Complete binary tree - basically make sure all the nodes are to the left of any ‘missing’ nodes i.e. where there are no nodes
How can a heap be used as a priority queue?
Store a (key, element) pair at each node
Keep a track of the position of the last node
How do you insert into a heap?
Find the insertion node z (the new last node i.e. at the lowest depth and to the left of that node, if possible)
Store the key at the new node z
Restore the heap order property afterwards
What is upheap and how does it work?
A heap-order property restoring method
After the insertion of a new key, the upheap swaps the new key along an upward path from the insertion node
This terminates when the key reaches the root of a node whose parent has a key smaller than or equal to itself.
Upheap runs in O(log n) time
How do you remove the root node from a heap?
Replace the root key with the key of the last node (called w)
Remove w’s original node
Restore the heap-order property
What is downheap and how does it work?
After replacing the root key with the key of the last node (k), downheap will restore the heap-order property by swapping the key k along a particular downward path from the root (looks for the smallest child node from the root, and swaps with that)
Terminates when key k reaches a leaf or a node whose children have keys greater than or equal to k
Downheap runs in O(log n) time
How do you implement a heap as an array?
Represent the heap with n keys by means of an array with length n+1
Links between nodes are not stored, but instead:
For the node at index i:
the left child is at index 2i
the right child is at index 2i+1
the parent is at index i/2
The cell at index 0 is not used
How do you insert, remove the minimum and perform upheap and downheap operations on an array-based heap?
Insert - inserting at index n+1
RemoveMin - moving index n to index 1
Up and down heap operations just swap appropriate elements within the array
How does a priority queue work within a heap?
To insert, insert in the heap as per normal (left-most node if possible, at the lowest depth)
To get the value with the minimal key, ask for the value of the root of the heap
To dequeue the highest priority item, remove the root and return the value stored there.
What is a heap-sort, and how does it work?
Consider a priority queue with n items implemented by means of a heap:
The space used is O(n)
Insert and removeMin take O(log n)
Methods size, isEmpty and min take O(1)
Using a heap-based priority queue, we can sort a sequence of n elements in O(n log n) time, and the resulting algorithm is called heap-sort.
What are the two stages of a heap-sort?
Insert all elements into the heap one by one. This takes n insertions with O(log n), each for a total of O(n log n)
Remove all elements one by one, using removeMin(), hence obtaining them in sorted order, which takes n removals with O(log n) each for a total of O(n log n).
