Heap Sort implementation time complexity

Question

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;
 }
}

• ratchet freak: 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
• coderodde: Your heapsort sorts [60, 1, 80, 64, 9, 94, 23, 88, 77, 98] incorrectly.
• Kanagavelu Sugumar: @coderodde ooh yeah it did mistake [1, 9, 23, 60, 64, 77, 80, 88, 98, 94], Thanks! i will check on it.

Answer 1

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.