Respuesta :
Answer:
Condition to break: [tex]H[j] \geq max {H[2j] , H[2j+1]}[/tex]
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[tex] and we need to check this:
Break condition: [tex]H[j] \geq max {H[2j] , H[2j+1]}[/tex]
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 [tex]j =1,2,.....,[n/2]p[/tex] 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).
