HeapSort Problem - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

HeapSort Problem

justinmejustinme Posts: 2Member
Got a question for heapsort need to handle in short time


input array A[1.....n]

Sorting algorithms should compute a sorting permutation pi[1...n]

which satisfies the following (1) it is permutation ie pi[i] belong
{1...n} and for all i != j hava pi[i]! = pi[j] (2) pi sorts (i.e) if we filled an array B[1...n] by placing A[i] into B[pi[i]] then B would be in sorted order.

for example if A= [ 8,5,11,6] the sorting permutation would be [3,1,4,2] since in the sorted array "8" should be in position 3, "5 " should be in position 1 etc.


Show how to modify Heapsort such that it leaves the input
array A unchanged and computess the sorting permutation pi

instead You may assume that all input integers are distinct. You should have O (nlog n) worst-case run time.


thanks for helppp!!!!!
Sign In or Register to comment.