Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Notifications
Mark all as read
Q&A

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```
Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

2 comment threads

"Heapify" is just the process of building the "max heap"... (3 comments)
Please fix the formatting (1 comment)

1 answer

+4
−0

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.

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

Sign up to answer this question »