HeapSort theory?

Question

I am not using HeapSort to sort an array that is already filled, but am using HeapSort as the array is filled.

For a heap where the smallest values are at the top, my understanding was that when you insert a new value to the heap you checked the parent node to see if the new child is larger. If it is you do nothing, if it isn't you check and swap as need up the tree?

Is this not right because my implementation of it is not working at all:

public class HeapSort{
 static int[] numbers = new int[] { 0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
 static int[] array = new int[16];

 public static void main(String[] args) {
    for (int i = 1; i < 15; i++) {
        array[i] = numbers[i];
        if (i > 1)
            sort(i);
    }
    for (int i = 1; i < 15; i++) {
        System.out.println(array[i]);
    }
 }

 public static void sort(int i) {
    int parentLocation = i / 2;
    int childLocation = i;

    int parentValue = array[parentLocation];    
    int childValue = array[childLocation];

    if(parentValue > childValue){
        array[parentLocation] = childValue;
        array[childLocation] = parentValue;
    }
    if(parentLocation != 1){
        sort(parentLocation);
    }
  }
}

TIA

If its anyhelp this is the output when I give it 1-15 backwards:

2
6
3
9
7
5
4
15
12
13
8
14
10
11

But you all seem as stumped as I am!

Answer 1

It looks like your not sorting the entire array. Say that you have 10 fields correctly sorted and you insert number. So you have
-, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11 and insert 10 (should go second last and the - is cause you never put anything there)

Now your algorithm compares parentLocation 5 (11/2) and childLocation 11 right? Well, 5 is smaller than 11 so nothing is swapped. Then you continue to sort again with input 5.

This time you compare parentLocation 2 (5/2) and childLocation 5. 2 is smaller than 5, still not change.

Until done. But you never test to see if 10 and 11 is in the correct order at all, you start half way down.

Easiest fix is to change your two iterations to

for (int i = 1; i < numbers.length; i++) {...}
...
for (int i = 1; i < array.length; i++) {...}

As your missing the end positions in your current code.
Then change the first line in sort() to

int parentLocation = i - 1;

That way your recursive check checks the entire array. But this is regular sorting, nothing heapy about it :)

Added complete new solution :) I'm sure this is not the optimal solution but it's easy to follow. I've replaced the target heap with an ArrayList to be able to shrink it easy.

package se.wederbrand.stackoverflow;

import java.util.ArrayList;

public class HeapSort {
  static int[] numbers = new int[]{0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  static ArrayList<Integer> heap = new ArrayList<Integer>();

  public static void main(String[] args) {
    // add 0 at the first position
    heap.add(0);
    for (int i = 1; i < numbers.length; i++) {
      heap.add(numbers[i]);
      if (i > 1) {
        reheapifyBottomUp(i);
      }
    }
    while (heap.size() > 1) {
      System.out.println(removeFirstFromHeap());
    }
  }

  private static int removeFirstFromHeap() {
    // the value at index 1 should be returned
    int returnValue = heap.get(1);

    // the last node is replacing the removed one
    if (heap.size() > 2) {
      heap.set(1, heap.remove(heap.size() - 1));
      reheapifyTopDown(1);
    }
    else {
      heap.remove(1);
    }

    return returnValue;
  }

  public static void reheapifyBottomUp(int childLocation) {
    int parentLocation = childLocation / 2;

    int parentValue = heap.get(parentLocation);
    int childValue = heap.get(childLocation);

    if (parentValue > childValue) {
      heap.set(parentLocation, childValue);
      heap.set(childLocation, parentValue);
    }
    if (parentLocation != 1) {
      reheapifyBottomUp(parentLocation);
    }
  }

  public static void reheapifyTopDown(int parentLocation) {
    int childLocation1 = parentLocation * 2;
    int childLocation2 = childLocation1 + 1;

    int parentValue = heap.get(parentLocation);
    int childValue1 = Integer.MAX_VALUE;
    if (heap.size() > childLocation1) {
      childValue1 = heap.get(childLocation1);
    }
    int childValue2 = Integer.MAX_VALUE;
    if (heap.size() > childLocation2) {
      childValue2 = heap.get(childLocation2);
    }

    if (childValue1 <= childValue2 && parentValue > childValue1) {
      // swap them and continue down
      heap.set(parentLocation, childValue1);
      heap.set(childLocation1, parentValue);
      reheapifyTopDown(childLocation1);
    }
    else if (childValue2 < childValue1 && parentValue > childValue2) {
      // swap them and continue down
      heap.set(parentLocation, childValue2);
      heap.set(childLocation2, parentValue);
      reheapifyTopDown(childLocation2);
    }
  }
}

Answer 2

Your sort method should be renamed as heapify(). Your current sort() method is just re-arranging the heap.

A min/max heap is never sorted, and hence you can never traverse it the way you can traverse Binary Search Tree. You will have to implement something like removeMin() which will remove the topmost element from the heap and the sort the remaining heap.

Answer 3

All you have done here is add a bunch of numbers to a heap (which looks correct at first glance). The array contains values in a heap -- not a sorted list. To get the sorted list out, in heap sort, you need to keep popping the smallest element and re-heaping. You're missing this step; you're just printing out the final heap before you start that process.