Chapter 6 (Priority Queues (Heaps)) Flashcards
What is the big-O time to search for a min in a linked list?
O(n) since you might have to search the whole list
What is the insert and remove min for a binary heap?
O(log n)
When is a binary tree complete?
Every node has two children except the last level which is filled from left to right
How does a sorted linked list affect the search for a min and inserting?
Search for a min becomes O(1) since it’s sorted, but insert becomes O(n) because it may have to traverse to the end of the list for the insert.
T/F The npl of any node is two more than the minimum npl’s of its children
F, one more
What is the NPL of a null?
-1
Where is the maximum value in the heap-order property?
In a leaf node
What’s the difference between a leftist heap and skew heap?
The skew heap does not compare left and right subtree’s, it always swaps after a merge no matter what.
T/F The structure of a heap is a binary tree that is completely filled except possibly the bottom level, which is filled left to right
T
What are two operations that a priority queue, at the minimum, supports?
Insert (enqueue) and deleteMin (similar to dequeue)
When is a binary tree perfect?
Has exactly 2^(h+1)-1 nodes where h is the height
What does a delete need?
decreaseKey to minimum then deleteMin
Since there are at most log N different trees, each with its minimum at its root, the heap’s minimum can be found in ____ time
O(log N)
Leftist heaps use a ____ of a node, which is the length of the shortest path from the node to a node without two children
“null path length”
What is the NPL of a node with 0 or 1 child?
0
What does decreaseKey require?
Percolate up
With the heap-order property, what is the running time for the findMin operation?
O(1)
What does increasKey require?
Percolate down
What two things have to be done for deleteMin?
Remove the root value Re-arrange the heap to preserve the heap-order property
What is a d-heap?
Has d children per parent
What is the running time of buildHeap?
O(N)
T/F Each item in a queue is treated equally
T
What is the advantage of a d-heap having d children?
Results in a shallower tree, which improves performance of inserts
What two things must be done for an insert with a binary heap?
Insert into the next available node Re-arrange the heap to preserve the heap-order property