Question

For binary heap, heapify-up, heapify-down, insert, delete min/max, heap sort

pls give examples with solutions in C

Answer 1

Answer:

The complete code for heap sort is given below, which includes insert/delete, and heapify.

please have a look and let me know if further assistance is required.

code:

#include <iostream>
using namespace std;

void heapifyArray(int array[], int a, int m) // a is the size of the heap, hepify will be done of the root node with the node present at the index m
{
int large = m; // Root will be initialized as largest
int leftChild = 2*m + 1; // Assign left child
int rightChild = 2*m + 2; // Assign right child

  
if (leftChild < a && array[leftChild] > array[large]) // If left child is bigger than the root
large = leftChild;

  
if (rightChild < a && array[rightChild] > array[large]) // If right child is bigger than the root
large = rightChild;

  
if (large != m) // If the root is not the largest of all
{
swap(array[m], array[large]); //swap the values

  
heapifyArray(array, a, large); // Recursion is applied here to hepify the rest
}
}

void sortHeap(int array[], int a) //fucntion definition of heap sort function
{
  
for (int m = a / 2 - 1; m >= 0; m--) // This will build a heap
heapifyArray(array, a, m);

  
for (int m=a-1; m>=0; m--) // This will extract the elements from the heap
{
  
swap(array[0], array[m]); // Send root element to the bottom of almost complete binary tree


heapifyArray(array, m, 0); // Now again do the hepify operation to do build heap
}
}

void displayArray(int array[], int length) // To display the array
{
for (int i=0; i < length; i++)
printf("%d ", array[i]);
printf("\n");
}


// Main function is given below
int main()
{
int array[] = {45, 32, 87, 2, 6, 99, 39, 76, 54, 19, 36, 12}; // Array declaration with initialization
int a = sizeof(array)/sizeof(array[0]); // For calculating current size fo the given array
sortHeap(array, a); // Function of Insertion Sort is called here
printf("Sorted array: \n"); // Displaying the sorted array
displayArray(array, a); // To display the array
return 0;
}

Output:

Sorted array: 2 6 12 19 32 36 39 45 54 76 87 99 Process exited after 0.1711 seconds with return value e Press any key to continue

Please give it a thumbs up if this helped you, also provide your valuable feedback.