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.
Regarding the heap sort algorithm.
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```
1 answer
As you know, a max heap is a binary tree such that each parent is greater than its children.
The most compact and efficient way to represent such a tree is an array, where each index corresponds to a node in the tree, numbered from the root, level by level, from left to right, as shown in the following picture:
0
/ \
/ \
1 2
/ \ / \
3 4 5 6
Then, if a node is stored at index i, we know that its left child is stored at index i * 2 + 1, and its right child at index i * 2 + 2.
This representation has the advantage that we do not need any pointers to represent the structure of the tree, allowing for a more compact memory layout.
The sort proceeds by taking the numbers in an array, reinterpreting that array as an encoded max heap, and moving elements around until the heap invariant (that each parent is greater than both of its children) is satisfied.
The heapify function takes an index i, and checks that the node stored there is greater than its children. If this is not the case, the greater child swaps places with the parent. Since this swap reduces the value of the child, it is possible that the child is no longer greater than its children, so we recursively check them (again).
More precisely, the heapify function assumes that the subtrees of the children are correct (each node greater than its children), and makes sure the entire tree rooted at i is correct. By invoking heapify for each node, from bottom to top, we therefore ensure the entire tree is correct.
And that's why the function is called heapify: It turns our unsorted array into an encoded max heap.
0 comment threads
2 comment threads