search
Log In
0 votes
20 views

Argue the correctness of HEAPSORT using the following loop invariant:

At the start of each iteration of the for loop of lines $2–5$,the subarray $A[1..i]$ is a max-heap containing the $i$ smallest elements of $A[1..n] $, and the subarray $A[i+1..n]$ contains the $n- i$ largest elements of $A[1..n]$, sorted.

 

in Algorithms 20 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
0 votes
0 answers
2
22 views
What is the running time of HEAPSORT on an array $A$ of length $n$ that is already sorted in increasing order? What about decreasing order?
asked Jun 27, 2019 in Algorithms akash.dinkar12 22 views
0 votes
0 answers
3
49 views
HEAPSORT(A) 1 BUILD-MAX-HEAP(A) 2 for i = A.length down to 2 3 exchange A[1] with A[i] 4 A.heapsize=A.heapsize – 1 5 MAX-HEAPIFY(A,1) illustrate the operation of HEAPSORT on the array $A=\langle 5,13,2,25,7,17,20,8,4 \rangle$
asked Jun 27, 2019 in Algorithms akash.dinkar12 49 views
0 votes
0 answers
4
...