Description
Lab4 exercises your understanding of the Heap Data Structure and Heapsort
Follow these steps:
1) place the given and requested code in file L5.cpp and upload when completed to Canvas
2) allocate an array A of ‘N + 1’ where N is a positive number; ignore index 0 and treat elements indexed 1 through ‘N’ as potential nodes in a MAXheap
3) place the following code into an insertion function, complete the function definition and then construct a heap with multiple random values
numItems++;
A[numItems] = x;
int k = numItems;
while (k>1 && A[k] > A[k/2])
{ swap( A[k], A[k/2]);
k = k/2;
}
4) place the following code into a ‘heapifyDown’ function, complete the function definition
while (2*k <= numItems && !done)
{ int lrg = k;
if (A[2*k] > A[k]) lrg = 2*k; //left child > parent
if (2*k+1<=numItems && A[2*k+1] > A[lrg]) // rtchild largest
lrg = 2*k + 1;
if (lrg != k) // parent not largest
{ swap( A[k], A[lrg]);
k = lrg;
}
else done = true;
}
5) using function ‘heapifyDown’, construct AND test a deletion function
6) Heapsort is a sorting algorithm that can viewed as the following steps:
a. N = numItems
b. swap the largest item (root) of the heap with the item in the last position
swap(A[1], A[N])
c. decrement N (but leave data value in A[N]
d. heapifyDown
e. repeat steps a-c until heap is ‘empty’
f. A[1]..A[numItems] now contains sorted array
7) Write and test Heapsort
