javaheapsort

Why (n/2)-1 in heap sort?


In heap sort, while rearranging an array in for loop why we need i=n/2-1 and I checked with n/2 also it worked as expected.

 // Build heap (rearrange array) 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 

Instead, I used like below:

// Build heap (rearrange array) 
    for (int i = n / 2; i >= 0; i--) 
        heapify(arr, n, i); 

Below is the full program,

// Java program for implementation of Heap Sort 
public class HeapSort { 
public void sort(int arr[]) 
{ 
    int n = arr.length; 

    // Build heap (rearrange array) 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 

    // One by one extract an element from heap 
    for (int i=n-1; i>=0; i--) 
    { 
        // Move current root to end 
        int temp = arr[0]; 
        arr[0] = arr[i]; 
        arr[i] = temp; 

        // call max heapify on the reduced heap 
        heapify(arr, i, 0); 
    } 
} 

// To heapify a subtree rooted with node i which is 
// an index in arr[]. n is size of heap 
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // Initialize largest as root 
    int l = 2*i + 1; // left = 2*i + 1 
    int r = 2*i + 2; // right = 2*i + 2 

    // If left child is larger than root 
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 

    // If right child is larger than largest so far 
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 

    // If largest is not root 
    if (largest != i) 
    { 
        int swap = arr[i]; 
        arr[i] = arr[largest]; 
        arr[largest] = swap; 

        // Recursively heapify the affected sub-tree 
        heapify(arr, n, largest); 
    } 
} 

/* A utility function to print array of size n */
static void printArray(int arr[]) 
{ 
    int n = arr.length; 
    for (int i=0; i<n; ++i) 
        System.out.print(arr[i]+" "); 
    System.out.println(); 
} 

// Driver program 
public static void main(String args[]) {
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int n = arr.length; 
    HeapSort ob = new HeapSort(); 
    ob.sort(arr);
    System.out.println("Sorted array");
    printArray(arr); 
} }

Solution

  • A complete binary heap of height h has 2^h - 1 elements. Of those, elements in the closed range [0, (2^h)/2-1] are internal nodes (including the root), and elements in the closed range [(2^h)/2, 2^h-2] are leaf nodes. The leaf nodes are already (trivial) heaps. The first element you need to heapify -- because it has a child, which might violate the heap property -- is at index (2^h)/2-1.

    This property -- that the highest-index internal node is slightly below the halfway point -- extends to incomplete binary heaps as well. Draw out a few heaps and you'll see the pattern.