Problem 2. Two Binary Min Heap Algorithms For both of these problems, for full c
ID: 3877403 • Letter: P
Question
Problem 2.
Two Binary Min Heap Algorithms For both of these problems, for full credit your solution should be the most efficient possible. Perhaps in the worst case they might need to examine every element in the heap, but in general this should not be the case. You may assume an array layout of the binary min heap as discussed in lecture. You also may assume that your algorithm has direct access to the heap array (it does not need to manipulate it just by using the standard heap operations insert, deletemin, findmin, etc.). Your algorithm should not modify the heap (just like a findmin does not modify the heap) or at the very least, if it does, it should put it back identical to how it was before you started. Be sure to answer all four parts (a-d) of the question!
a) Write pseudocode for an efficient algorithm that will find the maximum value in a binary min heap.
b) What is the worst case complexity of the algorithm you wrote in part (a)? Give your answer in big-O.
c) Write pseudocode for an efficient algorithm that will find all values less than a given value in a binary min heap. Your algorithm should just print out the values it finds. Note that the “given value" is not necessarily in the heap. We could ask you to find all values less than 42 in the heap, where the value 42 is not in the heap.
d) What is the worst case complexity of the algorithm you wrote in part (c)? Give your answer in big-O. What is the runtime of your algorithm if it finds k values less than the input value?
Explanation / Answer
Answer:
a) See the pseudocode below:
-----------------------------------------------------------
1. Algorithm getMax()
2. //Algorithm to get maximum of a min-heap of n elements. Assume heap is being represented as an array.
3. {
4. duplicate_heap = createHeapCopy(); //create a copy of heap. it will an array.
5. sort(duplicate_heap); //sort the array in decending order
6. max = duplicate_heap[0]; //max element of array
7. return max;
8. }
b) Complexity of an algorithm depends on the key operations in algorithm. Key operation in the algorithm given above is sorting of temporary array. Worst case complexiting of sorting an array of n elements is O(n2). Hence, the worst case complexity of the algorithm of part a) will be O(n2).
c) See the pseudocode below:
-------------------------------------------------
1. Algorithm printValuesLessThanX(m)
2. //This algorithm prints all values from a min-heap that are less than m,
3. {
4. while(heap has elememts) //loop to extract elements for loop
5. {
6. x = extractMin(); //extract minimum element from heap
7. if (x < m) //check if x is less than m.
8. {
9. print(x); //print x
10. }
11. }
12. }
d) As explained in part b, the complexity of an algotithm depends on the performance of its key operations. Key operation in the algorithm of part c) is loop to extract minimum elements of heap one by one. Worst case complexity of this loop will be O(n) where n is the number of elements in min-heap. Hence, worst case complexity of the algorithm will be O(n). Here is assumed that extractMin() process will take unit time.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.