Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Comments on Regarding the heap sort algorithm.
Post
Regarding the heap sort algorithm.
+1
−3
I get the concept of the heap sort algorithm and its like first you have a heap(ordered binary tree) then we have the Max heap which has the highest element value in the array at the top of the tree. The parent nodes will be basically > than the child nodes. But I don't get the heapify sample code here. Can someone explain? Thank you.
#include <stdio.h>
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
//can someone explain the heapify function of the coding?
void heapify(int arr[], int n, int i) {
int max = I;
int leftChild = 2 * i + 1; coding
int rightChild = 2 * i + 2;
//If left child is greater than root
if (leftChild < n && arr[leftChild] > arr[max])
max = leftChild;
//If right child is greater than max
if (rightChild < n && arr[rightChild] > arr[max])
max = rightChild;
//If max is not root
if (max != i) {
swap(&arr[i], &arr[max]);
//heapify the affected sub-tree recursively
heapify(arr, n, max);
}
}
//Main function to perform heap sort
void heapSort(int arr[], int n) {
//Rearrange array (building heap)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
//Extract elements from heap one by one
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]); //Current root moved to the end
heapify(arr, i, 0); //calling max heapify on the heap reduced
}
}
//print size of array n using utility function
//print size of array n using utility function
void display(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
//main function coding not included```
2 comment threads