Build a heap and and implement heapsort in C code. a)Write a C program that rece

Question

Build a heap and and implement heapsort in C code.

a)Write a C program that receives an array with a (size < 100) and produces its max binary heap. The function should follow this algorithem :

heap Max-Heapify (A, i):
left 2*i // means "assignment"
right 2*i + 1 largest i

if left heap_length[A] and A[left] > A[largest] then:
largest left

if right heap_length[A] and A[right] > A[largest] then:
largest right

if largest i then:
swap A[i] and A[largest]
Max-Heapify(A, largest)

b)Implement healpsort algorithm where it receives an array and its size and sorts that array. Your code should print the sorted array at the end of the main function.

This function should be in the form of void heap_sort_algorithm( double *a, int count) and do the following:

1. Call the buildMaxHeap() function on the list. Also referred to as heapify(), this builds a heap from a list in O(n) operations.
2. Swap the first element of the list with the final element. Decrease the considered range of the list by one.
3. Call the siftDown() function on the list to sift the new first element to its appropriate index in the heap.
4. Go to step (2) unless the considered range of the list is one element.

Explanation / Answer

/* Heap Sort Algorithm Implementation in C */

#include <iostream.h>
#include <stdio.h>
using namespace std;

void max_heapify(int *a, int i, int n) {
   int j, temp;
   temp = a[i];
   j = 2*i;
    while (j <= n) {
       if (j < n && a[j+1] > a[j])
            j = j+1;
       if (temp > a[j])
            break;
        else if (temp <= a[j]){
            a[j/2] = a[j];
            j = 2*j;
        }
    }
    a[j/2] = temp;
    return;
}

void heapsort(int *a, int n){
   int i, temp;
    for (i = n; i >= 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(void) {
   int n, i, x;
   printf("Enter no of elements of array ");
   cin>>n;
   int a[20];
   for (i = 1; i <= n; i++) {
       printf("Enter element (%d) . ", i);
       scanf("%d", &a[i]);
   }
   build_maxheap(a,n);
   heapsort(a, n);
   printf("sorted output ");
   for (i = 1; i <= n; i++) {
       printf("%d ", a[i]);
    }
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

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