current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 3 down vote favorite
1

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;
    }
}
share|improve this question
    
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 – ratchet freak Apr 22 at 12:02
    
Your heapsort sorts [60, 1, 80, 64, 9, 94, 23, 88, 77, 98] incorrectly. – coderodde Apr 22 at 12:16
    
@coderodde ooh yeah it did mistake [1, 9, 23, 60, 64, 77, 80, 88, 98, 94], Thanks! i will check on it. – Kanagavelu Sugumar Apr 22 at 12:19
up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks for the program! – Kanagavelu Sugumar Apr 22 at 19:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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