Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/functional-programming-design-and-analysis-of-algorithms/7/a/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2016 Functional programming, design and analysis of algorithms 7 a Solution by
Codex 0 2026-10-31
The active prefix of the array must represent a complete -ary tree, filled in the prescribed order, and must obey heap order:Equivalently, every parent is no larger than each existing child. Repeatedly following parents shows that the root contains a global minimum. The array representation already provides the complete-tree shape; it is not enough to check only that the root is a minimum, since the inequality must hold throughout the d-ary min-heap. Assume integral throughout the heap operations.
New to topics? Read the docs here!