Write a pseudocode to generate a minheap from a given array

Write a pseudo-code to generate a min-heap from a given array A. State the run time complexity of your algorithm.

Please answer the complete question. I will rate complete answers! Thank you!!

Solution

Hi,

The algorithem would be as follows:

Build-MinHeap(A, n)
1: Build-MinHeap0(A, n, 1)
Build-MinHeap0(A, n,i)
1: if 2i n then
2: Build-MinHeap0(A, n, 2i)
3: if 2i + 1 n then
4: Build-MinHeap0(A, n, 2i + 1)
5: Min-Heapify(A, n,i)

Actually in the algorithm we first turn each of the subtrees of the root into a min-heap. Then there is only one spot where violation of the min-heap property may exist, which is the root. If we execute Min-Heapify from the root, then such violation will be eliminated.(we can call it a divide and conquer implementation)

This is the treditional algorithm of min heapify:

Max-Heapify(A, n,i)
1: k i
2: while k n/2 do
3: { k\' 2k
4: -> Set k\' to the left child for now
5:        if (k\' + 1 n and A[k\'] > A[k\' + 1])
6:            then k\' k\' + 1
7: -> If the right child exists and it has a smaller key
8: -> than the left child, k\' is the right child
9:        if A[k] > A[k\'] then
10:    { x A[k]; A[k] A[k\']; A[k\'] x }
11: -> Swap A[k] and A[k\'] if A[k\' > A[k]
12:    k k\'
13: -> Move to k\'
14: }

where A is the given array and n is the length of the array i is the index. For each node there will be a min heapify call and sequentically for every sub tree.So, if you don\'t want the recursion algorithm you can simply use

1: for i n/2 downto 2 do
2: Max-Heapify(A, n,i)

this algorithm for instead of first one may be you can understand this one better, both do same work

Here comes the time complexity:

The height of the heap is O(log n), so each call to Min_heapify costs O(log n).Since there are n calls for heapify (i.e., we are calling heapify for every node of the array) the total cost is O(n log n).

That\'s all;Any further clarification needed you can commet below;