3
\$\begingroup\$

I have implemented Heap sort, but i think the time complexity is more than (nlogn). Could anyone explain me; what is wrong in my code which makes more time complexity.

I will be glad if the answer is in terms of algorithm time complexity based.

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] array = { 5, 6, 10, 3, 9, 2, 12, 1, 8, 7 };
        maxHeapSort(array, array.length);
        System.out.println(Arrays.toString(array));
        System.out.println("\n\n");
    }

    private static void maxHeapSort(int[] array, int length) {
        for(int i = 1; i < length; i++ ) {
            maxHeapify(array, 1, length-i);
            swap(array, 0, length-i);
        }
        //Working on last three indexes [which is 0,1,2]
        correctNode(array, 1, 3);
        swap(array, 0, 2);
        correctNode(array, 1, 2);
        swap(array, 0, 1);
    }

    private static void maxHeapify(int[] array, int nodeIndex, int length) {
        if(nodeIndex < length) {
            correctNode(array, nodeIndex, length);
            maxHeapify(array, 2 * nodeIndex, length);
            maxHeapify(array, (2 * nodeIndex)+1, length);
            correctNode(array, nodeIndex, length);
        }
    }

    private static void correctNode(int[] array, int index, int length) {
        int rootIndex = index - 1;
        int leftIndex = (2 * index) - 1;
        int rightIndex = ((2 * index) + 1) - 1;
        if(leftIndex < length && array[rootIndex] < array[leftIndex]) {
            swap(array, rootIndex, leftIndex);
        }

        if(rightIndex < length && array[rootIndex] < array[rightIndex]) {
            swap(array, rootIndex, rightIndex);
        }
    }

    private static void swap(int[] array, int m, int n){
        int temp = array[m];
        array[m] = array[n];
        array[n] = temp;
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ max heapify seems to run in O(n) and you do it O(n) times resulting in O(n^2), the cause is the double recursion. you should only need to recurse down one branch \$\endgroup\$ – ratchet freak Apr 22 '16 at 12:02
  • \$\begingroup\$ Your heapsort sorts [60, 1, 80, 64, 9, 94, 23, 88, 77, 98] incorrectly. \$\endgroup\$ – coderodde Apr 22 '16 at 12:16
  • \$\begingroup\$ @coderodde ooh yeah it did mistake [1, 9, 23, 60, 64, 77, 80, 88, 98, 94], Thanks! i will check on it. \$\endgroup\$ – Kanagavelu Sugumar Apr 22 '16 at 12:19
2
\$\begingroup\$

correctNode() looks like an (algorithmic) code-smell: its not needed. The only routines required to implement heap sort are:

  1. swap
  2. maxHeapify for maintaining the max-heap invariant; the topmost invocation must run in \$\mathcal{O}(\log n)\$.
  3. buildMaxHeap, Introduction to Algorithms has a funky proof that this runs in linear time. Since, it is called only once, linear time is OK.
  4. The actual heap sort routine: builds the max heap and pops in order until sorted.

The length argument of your heap sort is not needed. You can alwasy ask array.length.

I had this in mind:

public static void sort(final int[] array) {
    buildMaxHeap(array);
    int heapSize = array.length;

    for (int i = array.length - 1; i > 0; --i) {
        swap(array, 0, i);
        maxHeapify(array, 0, --heapSize);
    }
}

private static void buildMaxHeap(final int[] array) {
    for (int i = array.length / 2; i >= 0; --i) {
        maxHeapify(array, i, array.length);
    }
}

private static void maxHeapify(final int[] array, 
                               final int index,
                               final int heapSize) {
    final int leftChildIndex = (index << 1) + 1;
    final int rightChildIndex = leftChildIndex + 1;

    int largestIndex;

    if (leftChildIndex < heapSize 
            && array[leftChildIndex] > array[index]) {
        largestIndex = leftChildIndex;
    } else {
        largestIndex = index;
    }

    if (rightChildIndex < heapSize
            && array[rightChildIndex] > array[largestIndex]) {
        largestIndex = rightChildIndex;
    }

    if (largestIndex != index) {
        swap(array, largestIndex, index);
        maxHeapify(array, largestIndex, heapSize);
    }
}

private static void swap(final int[] array, 
                         final int index1, 
                         final int index2) {
    final int tmp = array[index1];
    array[index1] = array[index2];
    array[index2] = tmp;
}

Hope that helps.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.