Describe an 0(1) algorithm that finds a the third largest value in a MAX heap. Y

Question

Describe an 0(1) algorithm that finds a the third largest value in a MAX heap. You may assume the heap size is >=3. Justify your algorithms performance.

Explanation / Answer

//Stores into n the larger of the root's children and n2 the smaller of the children Node n,n2; int thirdLargestValue; if(Root.Right.Value>Root.Left.Value) { n=Root.Right; n2=Root.Left; } else { n=Root.Left; n2=Root.Right; } //This accounts for the case that one of the root's grandchildren is the third largest value if(max(n.Left.Value,n.Right.Value)>n2.Value) { thirdLargestValue=max(n.Left.Value,n.Right.Value) } //Now the smaller of the root's children is the third largest value else { thirdLargestValue=n2.Value; } We never deal with the number of values in the heap, we only have 8 important commands either comparing values or storing values, and that number will be the same for any heap size, or CONSTANT. Since N(size of heap) is never used, the complexity of the algorithm is constant, and can therefore be represented by O(1).

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.