using c++ help me with the following problem Heapsort: Implement the heap sort i

Question

using c++ help me with the following problem

Heapsort:

Implement the heap sort in the form of a template function:

template <class T>
void heap_sort(T data[], int length)

The heapsort works in two phases: build a heap then destroy the heap.

1)   To build the heap, you consider the data array to hold a heap at the beginning of the array with un-heaped data after it
•   For example, at some stage the elements from index 0 to index 20 could form a heap while the elements from index 21 on are unprocessed.
•   Start with a heap of size 1 and the rest of the elements unprocessed
•   If the whole array is not yet a heap, insert the first element not in the heap into the heap. This really just means move it up towards the root, if necessary
•   Repeat the previous step until the whole array is ‘heapified’

2)   To destroy the heap, again the data array holds a heap followed by data not in the heap.
•   You start with the entire array in the heap
•   If there is anything left in the heap, remove the largest, swap the largest element in the heap (the first one) with the last element in the heap and then move the new first element down to its proper place
•   Repeat previous step until the heap is size one

Test the function in main().

Explanation / Answer

#include #include using namespace std; void max_heapify(int *a, int i, int n) { int j, temp; temp = a[i]; j = 2*i; while (j a[j]) break; else if (temp = 2; i--) { temp = a[i]; a[i] = a[1]; a[1] = temp; max_heapify(a, 1, i - 1); } } void build_maxheap(int *a, int n) { int i; for(i = n/2; i >= 1; i--) { max_heapify(a, i, n); } } int main() { int n, i, x; coutn; int a[20]; for (i = 1; i

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.