Thread: Help..Heapp..Heapp..

The only reason I know that [-1] isn't valid is because other's (myself included) have also had this same idea in the past, and it was discussed on another forum.

You may certainly reserve the right to not visit my personal webpage. I'm not particularly proud of it anyway as it's very web 1.0 (if that).
Anyway, here is the relevant code from my site, converted to C:

Code:

#define T int
void HeapSortDownHeap(T a[], int l, int r) {
    T tempItem = a[l];
    int child = (l<<1) + 1;
    while (child < r) {
        //use right child if it is bigger
        if ((child + 1 < r) && (a[child] < a[child + 1]))
            ++child;
        if (!(tempItem < a[child]))
            break;
        a[l] = a[child];
        l = child;
        child = (child<<1) + 1;
    }
    a[l] = tempItem;
}

void HeapSort(T a[], int n) {
    //build heap
    for (int i = n>>1; i >= 0; --i)
        HeapSortDownHeap(a, i, n);
    //extract max item successively
    for (int j = n-1; j > 0; --j) {
        Swap(a[0], a[j]);
        HeapSortDownHeap(a, 0, j);
    }
}

As you can see, it performs just one extra addition per loop iteration inside HeapSortDownHeap. Feel free to critique the code, by the way.
You'd be hard pressed to measure any performance difference in doing it by using [-1], and if it were ever a matter of performance, you'd switch algorithm.

Nice ASCII art btw!

Originally Posted by anduril462

And for the $64,000 question:

Try moving the rest of that swap (red line) inside the while loop.

Actually it is best as-is.
One of the more obvious yet slower ways to code heap sort is to downheap by performing repeated swaps:
To go from D, A, B, C to A, B, C, D you perform three swaps. Each swap consists of three assignments/copies, so that's 9 copies all up.

The techinque which both the OP and myself used is to shuffle the items instead:
You first set aside a copy of D, then assign A to where D was, B to where A was, and C to where B was, then put D in its place and you've done just 5 copies all up.

Of course when it comes to C++ and you have a type with a specialised std::swap then the other way wins. Hmm if only there were a way for the algorithm to know if a specialised std::swap is available. I'm kinda tempted to start my own thread asking this.

I think that the actual logic error is in the way he's building the heap. I suggest building it the O(n) way as done in my post above.