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
What is the leftist heap property?
For every node, the npl of its left child is at least as large as the npl of its right child
A right child’s number is ____ its parent’s number
2X+1
When is a binary tree full?
Every node is either a leaf or has two children
What are leftist heaps designed to support?
Efficient merging of two heaps
What does buildHeap do?
Takes N items and builds a heap
What type of data structure is a queue?
FIFO
What is the heap-order property?
Any node should be smaller than all of its descendants
What is the running time of insert and remove min for a balanced search tree?
O(log n)
What is “percolate up”?
Create a node, check ordering, if not OK then swap with parent, repeat until the node is in its proper position
A complete binary tree of height h always has between ____ and ____ nodes, which leads to performance of ____
2^h, 2^(h+1)-1, O(log N)
T/F A priority queue is a data structure that orders its items by priority
T
What other heap operations might we have?
decreaseKey increaseKey delete buildHeap
Binomial queues are essentially a forest of heap-ordered trees where each tree of height k has exactly ____ nodes, and there can be at most one tree of each height
2^k
What is “percolate down”?
Repeat sliding the hole node down until the last node value can occupy this node while preserving the heap-order property
Binomial queues have ____ time on insert, deleteMin, and merge, but have ____ average time on an insert
O(log N), O(1)
What is the disadvantage of a d-heap having d children?
deleteMin may suffer because finding minimum child of a node is now harder
What are the advantages of storing a heap in an array?
No links (pointers), operations to traverse are fast
A left child’s number is ____ its parent’s number
2X
Any parent number is ____
X/2
