Question

Outline an algorithm in **pseudo code** for checking whether an array H[1..n] is a heap and determine its time efficiency.

Answer 1

Answer:

Condition to break: $H[j] \geq max {H[2j] , H[2j+1]}$

Efficiency: O(n).

Explanation:

Previous concepts

Heap algorithm is used to create all the possible permutations with K possible objects. Was created by B. R Heap in 1963.

Parental dominance condition represent a condition that is satisfied when the parent element is greater than his children.

Solution to the problem

We assume that we have an array H of size n for the algorithm.

It's important on this case analyze the parental dominance condition in order to the algorithm can work and construc a heap.

For this case we can set a counter j =1,2,... [n/2] (We just check until n/2 since in order to create a heap we need to satisfy minimum n/2 possible comparisions$and we need to check this:Break condition: [tex]H[j] \geq max {H[2j] , H[2j+1]}$

And we just need to check on the array the last condition and if is not satisfied for any value of the counter j we need to stop the algorithm and the array would not a heap. Otherwise if we satisfy the condition for each $j =1,2,.....,[n/2]p$ then we will have a heap.

On this case this algorithm needs to compare 2*(n/2) times the values and the efficiency is given by O(n).