Question

Can you please explain loop invariant for Heapsort, in which Min-Heapify and Build-Min-Heap are correct

Answer 1

ANS: Loop Invariants- is a very simple powerful techniques. if algorithm or set of instruction is correct.the invariant is perform every node of heap property. the value of node is bigger than value of left and right children. there are following three important points-

Initialization- it is true prior to the first iteration of the loop.

Maintenance- it is true before an iteration of the loop ,it remains true before the next iteration.

Termination: when the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct. it is used mathmatical induction .

Algorithm-

Heap sort(A){

Build -max-heap(A)

for (i=A.length to down 2)

exchange(A[i],A[i])

A.heapsize = A. heap size-1

max-hepify(A,i)

}

Time complexity - O(nlogn).

min heapify - it is a complete binary tree.every node does not perform greater value of child nodes . every node does not contain a smalller value element than child node it is not min   heap.

Build min heap - is satisfies the heap property. the parent is less than or equal to child node .but max heap is opposite of min heap that parent is greater than to child node.

Algorithm-

Build -min-Heap(A)

heap-size [A] <----- length [A];

for i <---- length [A]/2 downnto 1

do min - Heapify (A,i);