Heap Sorting not producing a correct output

Question

I am writing a function to sort an array using heap sorting. So far I have:

template <typename Item, typename SizeType>
void heap_sort(Item data[], SizeType size) {
vector<int> v(data,data+size);
SizeType unsorted = size;

make_heap(v.begin(),v.end());

while(unsorted > 1) {
    --unsorted;
    swap(data[0], data[unsorted]);
    reheapify_down(data,unsorted);
}
}

and:

template <typename Item, typename SizeType>
void reheapify_down(Item data[], SizeType size) {
SizeType current(0), big_child;
bool heap_ok = false;

while(!heap_ok && 2*current+1 < size) {
    if(2*current+2 > size)
        big_child = 2*current + 1;
    else if(data[2*current+1] > data[2*current+2])
        big_child = 2*current+1;
    else
        big_child = 2*current + 2;

    if(data[current] < data[big_child]) {
        swap(data[current],data[big_child]);
        current = big_child;
    }
    else
        heap_ok = true;
}
}

When I run the program, it outputs an incorrectly sorted array though. Is there something that I am just missing or some error that I overlooked?

Answer 1

Just a few suggestions.

First, I'd write a small proxy class that does nothing but let you use 1-based indexing on your collection. All the index math used in heaps assumes 1-based indexing, and it's a lot easier to compensate for 0-based indexing in one place than throughout all the code. As it stands right now, I have a hard enough time following the indexing to be sure your reheapify_down is correct. It's certainly the right general idea, but it would take a lot of work to be certain all the math is right.

Second, I'd write a check_heap (or whatever) that you can use to verify both your make_heap and your reheapify_down (as an aside, I'd decide on either "make_heap" or "heapify", so the names would be either "make_heap" and "remake_heap", or else "heapify" and "reheapify").

Beyond that, however, it's hard to be certain of the problem, especially since you haven't included the code for your make_heap in the question. If it isn't working correctly, the rest has no hope.