Module 2: Priority Queues Flashcards
What is an ADT?
It describes storing information and operations on that information
What are the operations associated with a stack?
Pop and push
Extra operations include size(), isEmpty and top
What are the operations associated with a queue
enqueue - inserting an item
dequeue - deleting the oldest item
isEmpty, size and front are all extras
What is a priority queue?
A collection of items/associated operations in which each item has an associated priority
What are the operations associated with Priority Queues?
Insert - inserts an item associated with a priority
deleteMax - returns and deletes item of highest priority
How do you use a priority queue to sort an array
Add all items in array to priority queue
Use deleteMax to copy largest items first into the array (starting at index n-1)
What is the big-O complexity of priority queue operations if the PQ is implemented using an unsorted array?
insert => O(1)
deleteMax => O(n)
What is the big-O complexity of priority queue operations if the PQ is implemented using an sorted array?
insert => O(n)
deleteMax => O(1)
What are the properties of a max-heap?
Structural Property - All levels of a heap are completely filled before starting another level and levels are filled from left to right
Heap-Order Property - For any node i, the key of i’s parent is larger than i
What is the height of a heap with n nodes?
Theta(log(n))
How should heaps be stored?
As arrays, not as BTs
What is the index of a root node of a Heap?
A[0]
What is the index of a left child in a Heap?
A{2i + 1]
What is the index of a right child in a Heap?
A[2i + 2]
What is the parent of node i in a Heap?
Floor of (i-1)/2
