Priority Queues and Disjoint Sets Flashcards
What will be the output of the following program?
create an empty priotiy queue
Insert(18)
Insert(12)
Insert(14)
print(ExtractMax())
print(ExtractMax())
Insert(15)
print(ExtractMax())
Insert(10)
print(ExtractMax())
print(ExtractMax())
As an answer, provide a sequence of integers separated by spaces.
18 14 15 12 10
Assume that you know in advance that in your application there will be n calls to INSERT and sqrt(n) calls to EXTRACTMAX. Which of the following two implementations of the priority queue is preferable in this case?
a) Arrray
b) Sorted Array
https://drive.google.com/file/d/16oi6oPuwChggszcV67U0rmH_SjZ7kuON/view?usp=sharing
Is it a binary max-heap?
23
17 18
14 7 19 18
11 7 7 12 7
NO
Assume that initially a binary max-heap H contains just a single node with value 0. Then, for all i from 1 to n, we insert i into H. We do this by attaching a new element to some leaf of the current tree. What will be the height of the resulting tree?
a) Theta(n)
b) Theta(logn)
c) Theta(n^2)
Right! Each time we attach a new leaf to the only branch of the tree.
How many edges of this binary tree violate the min-heap property? In other words, for how many edges of the tree, the parent value is greater than the value of the child?
5
4 11
14 7 14 18
11 7 7 12 7
4
This binary tree contains 13 nodes, and hence we have 13 subtrees here (rooted at each of 13 nodes). How many of them are complete?
https://drive.google.com/file/d/1Vd6ShyrWv4f5nhcRHa15fwOpOImlFovW/view?usp=sharing
11
You can specify optional feedback like this, which appears after this answer is submitted.
Consider a complete binary tree represented by an array [19,14,28,15,16,7,27,15,21,21,5,2] How many edges of this tree violate the max-heap property? In other words, for how many edges of the tree, the parent value is smaller than the value of the child?
5
Assume that a max-heap with 10^5 elements is stored in a complete 5-ary tree. Approximately how many comparisons a call to Insert() will make?
a) 8
b) 18
c) 28
d) 38
Recall, that to insert a new element, we attach it as a leaf to the last level and let the new node sift up. The number of comparisons required to sift it up is at most the height of the tree. In this case, the height is log5(10^5) aprox 8.
Assume that a max-heap with 10^6 elements is stored in a complete 7-ary tree. Approximately how many comparisons a call to ExtractMax() will make?
a) 5
b) 50
c) 500
https://www.cs.usfca.edu/~galles/visualization/Heap.html
Recall, that to extract the maximum value, we replace the root node with the last leaf and let this new node sift down. When sifting its down, on each level we need to find the maximum among 7 children. Thus, the worst case running time of ExtractMax() in this case is 7*log(10^6) aprox 50.
Consider the following program:
for i from 1 to 12:
MakeSet(i)
Union(2,10)
Union(7,5)
Union(6,1)
Union(3,4)
Union(5,11)
Union(7,8)
Union(7,3)
Union(12,2)
Union(9,6)
print(Find(6))
print(Find(3))
print(Find(11))
print(Find(9))
Assume that the disjoint sets data structure is implemented as an array Smallest [1,…,12]: Smallest[i] is equal to the smallest element in the set containing i. What is the output of the following program? As an answer, enter four integers separated by spaces.
1 3 3 1
Consider the following program:
for i from 1 to 12:
MakeSet(i)
Union(2,10)
Union(7,5)
Union(6,1)
Union(3,4)
Union(5,11)
Union(7,8)
Union(7,3)
Union(12,2)
Union(9,6)
Assume that the disjoint sets data structure is implemented as disjoint trees with union by rank heuristic. Compute the product of the heights of the resulting trees after executing the code. For example, for a forest consisting of four trees of height 1, 2, 3, 1 the answer would be 6. (Recall that the height of a tree is the number of edges on a longest path from the root to a leaf. In particular, the height of a tree consisting of just one node is equal to 0.)
- Right! There will be 3 trees of height 1, 1, and 2.
Consider the following program:
for i from 1 to n:
MakeSet(i)
for i from 1 to n-1:
Union(i,i+1)
Assume that the disjoint sets data structure is implemented as disjoint trees with union by rank heuristic. What is the number of trees in the forest and the maximum height of a tree in this forest after executing this code? (Recall that the height of a tree is the number of edges on a longest path from the root to a leaf. In particular, the height of a tree consisting of just one node is equal to 0.)
a) Two trees, both of height 1
b) One three of height 1
c) One three of height log2(n)
d) log2(n) trees, the maximum height is 1
e) n trees, the maximum height is 1
f) n/2 trees, the maximum height is 2.
One three of height 1
Consider the following program:
for i from 1 to 60:
MakeSet(i)
for i from 1 to 30:
Union(i,2i)
for i from 1 to 20:
Union(i,3i)
for i from 1 to 12:
Union(i,5*i)
for i from 1 to 60:
Union(i)
Assume that the disjoint sets data structure is implemented as disjoint trees with union by rank heuristic and with path compression heuristic. Compute the maximum height of a tree in the resulting forest. (Recall that the height of a tree is the number of edges on a longest path from the root to a leaf. In particular, the height of a tree consisting of just one node is equal to 0.)
You know from the lectures that a heap can be built from an array of n integers in O(n) time. Heap is ordered such that each parent node has a key that is bigger than both children’s keys. So it seems like we can sort an array of n arbitrary arbitrary integers in O(n) time by building a heap from it. Is it true?
Yes
No
No
Although the key of each parent node is bigger than the keys of the children, the keys can be not ordered from the biggest to the smallest. For example, with just three numbers 312 the head element 3 is bigger than both children 1 and 2, but their relative order is wrong. Also, you should recall from the Algorithmic Design and Techniques class that it is impossible to sort n objects based only on results of comparisons of pairs of objects faster than in O(nlogn) time.
You’ve organized a party, and your new robot is going to meet and greet the guests. However, you need to program your robot to specify in which order to greet the guests. Of course, guests who came earlier should be greeted before those who came later. If several guests came at the same time or together, however, you want to greet first the older guests to show them your respect. You want to use a min-heap in the program to determine which guest to greet next. What should be the comparison operator of the min-heap in this case?
https://drive.google.com/file/d/1B7sYiUD5U2olknp1s4l2Sj7DagKkBI1r/view?usp=sharing
