PQ and Binary Heap Flashcards
What are the 3 implementations of Priority Queue?
- Circular Array (Quick Find)
- Circular Array (Quick Insert)
- Binary Heap
How does Circular Array (Quick Find) work?
Maintain a PQ by always inserting in the correct place. Front and Back index are maintained.
Time complexity of enqueue and dequeue of Circular Array (Quick Find)
Enqueue is O(N) as you search through the array to find a suitable insertion point and advance the back index. Dequeue is O(1) as you just dequeue from the front of the queue and advance the front index.
How does Circular Array (Quick Insert) work?
Same as Quick Find, but instead, you scan through the queue to find the item of the highest priority to dequeue.
Time complexity of enqueue and dequeue of Circular Array (Quick Find)
Enqueue is O(1) since you just insert to the back of the queue. Dequeue is O(N) since you have the search for the item of highest priority. You then need to close the gap, which is O(N).
2 Properties of a Binary Heap
- It’s a complete tree -> All levels are completely filled except for the last level, where all leaves are flushed to the left.
- For max heap, parent is always greater than children and for min heap, parent is always less than children.
What is the main implementation of a binary heap?
1-based array -> we start at index 1 because we can easily calculate the index of the right, left child and parent of any vertex
Time Complexity of Insert
O(logn) -> Insert to the last position and shift up
Time Complexity of ExtractMax
O(logn) -> Replace the first index with the last index, then shift down the last replaced value
Time Complexity of ShiftUp
O(logn) -> Traverse the height
Time Complexity of ShiftDown
O(logn) -> Traverse the height
Time Complexity of CreateHeap
O(N) -> Copy the content in O(N). For every parent -> O(N/2), shift it down O(logn)
Time Complexity of HeapSort
O(NlogN) -> Convert the array to a binary heap -> O(N) and pull out the items in order of priority -> O(N) x O(logn)
