Convert the following heapsort pseudocode to c++ code. Follow the psuedocode exa
ID: 3863500 • Letter: C
Question
Convert the following heapsort pseudocode to c++ code. Follow the psuedocode exactly.
BUILD MAX HEAP(A)
n= A.heapsize=A.length
for i = lower bound of (n/2) down to 1
MAXHEAPIFY(A,i)
-----------------------------------------------------
MAXHEAPIFY(A,i)
n=A.heapsize
l = left(i) <---- this is its own function
r = right(i) <---- this is its own function
if l <= n and A[l] > A[i]
largest = l
else
largest = i
if r <= n and A[r] >A[largest]
largest = r
if largest != i
exchange A[i] with A[largest]
MAXHEAPIFY(A, largest)
--------------------------------------------
heapSort(A,n)
n=A.heapsize = A.length
BUILDMAXHEAP(A)
for i = n down to 2
exchange A[0] with A [i]
A.heapsize= A.heapsize - 1
MAXHEAPIFY (A,1)
Explanation / Answer
code:
void build_max_heap(vector<int> A)
{
int n=A.size();
int i;
for(i=n/2;i>=1;i--)
max_heapify(A,i);
}
void max_heapify(vector<int> A)
{
int n= A.size();
int l =left(i);
int r = right(i);
if (l<=n &&A[l]>A[i])
largest=l;
else
largest =i;
if(r<=n &&A[r]>A[largest])
largest=r;
if(largest!=i)
{
swap(A[i],A[largest]);;
max_heapify(A,largest)
}
}
void heap_sort(vector<int> A,int n)
{
n = A.size();
build_max_heap(A);
int i;
for(i=n;i>=2;i--)
{
swap(A[0],A[i]);
A[i]=-1; //delete the last element or decrement the size of heap
max_heapify(A,1);
}
}