In chapter 6, we learned about one application of max heap is priority queue. As
ID: 3553226 • Letter: I
Question
In chapter 6, we learned about one application of max heap is priority queue. As seen in the textbook, there is a function Increase_key(s, x, k) where it is guaranteed that k >=s[x]. However, it is not the way reality is. Sometimes k could be smaller than s[x]. Please modify the Increase_key(s, x, k) function into Change_key(s, x, k) such that k could be any value, not just something greater than s[x]. < Hint: You might want to combine Max_Heapify and Increase_key function to generate this new function>
Explanation / Answer
Change_key(s,x,k){
if(k>=s[x]){
Increase_key(s,x,k);
}
else{
s[x] = k;
Max_Heapify(s, x);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.