educative.io

Educative

Seeking clarification in the given "Explanation" - Min Heap Implementation

In the Min Heap Implementation lesson, I had a question with respect to the “Explanation” -

Explanation:

This code covers all the cases that we discussed in the previous chapter. Let’s look at each function one by one and see what’s going on:

  • BuildHeap(): It takes the array and starts from the last child node (at the last level), then passes it to MinHeapify for comparison.
  • MinHeapify(): This functions takes the node value and compares it with the key at the parent node, and swaps them if the child node < the parent node. The while loop makes sure that the nodes keep swapping until we reach the last index and Heap property is satisfied throughout the Heap!

Here is the implementation code -

private void minHeapify(int[] heapArray, int index, int heapSize) {

        int smallest = index;

        while (smallest < heapSize / 2) { // check parent nodes only
            int left = (2 * index) + 1; //left child
            int right = (2 * index) + 2; //right child

            if (left < heapSize && heapArray[left] < heapArray[index]) {
                smallest = left;
            }
            if (right < heapSize && heapArray[right] < heapArray[smallest]) {
                smallest = right;
            }

            if (smallest != index) { // swap parent with smallest child
                int temp = heapArray[index];
                heapArray[index] = heapArray[smallest];
                heapArray[smallest] = temp;
                index = smallest;
            } else {
                break; // if heap property is satisfied
            }
        } //end of while
    }

    public void buildMinHeap(int[] heapArray, int heapSize) {
        // swap smallest child to parent node 
        for (int i = (heapSize - 1) / 2; i >= 0; i--) {
            minHeapify(heapArray, i, heapSize);
        }
    }

    public static void main(String[] args) {
        int[] heapArray = { 31, 11, 7, 12, 15, 14, 9, 2, 3, 16 };
        System.out.println("Before heapify: "+Arrays.toString(heapArray));      
        new Heap().buildMinHeap(heapArray, heapArray.length);
        System.out.println("After heapify: "+Arrays.toString(heapArray));
    }

So, when the buildMinHeap() function is called from within main(), it starts out at the last parent node which is at the middle index in the array and is calculated with this - int i = (heapSize - 1) / 2. This parent node is then compared with its children, and swaps are performed if necessary. Then we move on further left in the array (decrementing i towards 0) and repeat the process with other parent nodes.

Then, why does the description for the buildMinHeap() function state that “It takes the array and starts from the last child node (at the last level)”? This is wrong, because we start at the last parent node, and not the last child node.

Even the description for the minHeapify() function states that “This functions takes the node value and compares it with the key at the parent node”, whereas the node value is actually the parent node itself and we compare it with the child node, not the other way around.

Hi @Manish_Giri

Thank you so much for pointing it out and we have updated the course. Please let us know if you find anything else suspicious.