Removing elements from heap

Question

I made a heap. I am curious if there's something subtley wrong with my remove function:

int Heap::remove() {
    if (n == 0)
        exit(1);

    int temp = arr[0];
    arr[0] = arr[--n];
    heapDown(0);
    arr[n] = 0;

    return temp;
}

void Heap::heapDown(int i)
{
    int l = left(i);
    int r = right(i);
    // comparing parent to left/right child
    // each has an inner if to handle if the first swap causes a second swap
    //  ie    1   ->   3   ->   5
    //      3   5    1   5    1   3

    if (l < n && arr[i] < arr[l])
    {
        swap(arr[i], arr[l]);
        heapDown(l);

        if (r < n && arr[i] < arr[r])
        {
            swap(arr[i], arr[r]);
            heapDown(r);
        }
    }
    else if (r < n && arr[i] < arr[r]) 
    {
        swap(arr[i], arr[r]);
        heapDown(r);

        if (l < n && arr[i] < arr[l])
        {
            swap(arr[i], arr[l]);
            heapDown(l);
        }
    }
}

Here's my output

i1i2i3i4i5i6i7
p
Active heap: 7 4 6 1 3 2 5

r
Removed 7
r
Removed 6
p
Active heap: 5 3 4 1 2

Here's my teacher's sample output:

p
Active heap : 7 4 6 1 3 2 5
r   
Removed 7
r
Removed 6
p
Active heap : 5 4 2 1 3
s
Heapsorted : 1 2 3 4 5

While our outputs are completely different, I do seem to hold maxheap principle of having everything left oriented and for all nodes parent > child(in every case I tried). I try to do algs like this from scratch, so maybe I'm just doing something really weird and wrong (I would only consider it "wrong" if it's >O(lg n), as removes are intended to be for heaps). Is there anything in particular "wrong" about my remove? Thanks,

http://ideone.com/PPh4eQ

Solution

First, I assume you mean besides the fact that you don't need it, since we have an entire heap management function set in the C++ standard library, including make_heap, push_heap, pop_heap, and even sort_heap.

That said, I think I know what your problem is. You have unnecessary movement of elements in your heap. It deals with the swapping algorithm on the heap-down: the same problem is notable on both left and right sides, so I'll show the first one:

if (l < n && arr[i] < arr[l])
{
    swap(arr[i], arr[l]);
    heapDown(l);

    if (r < n && arr[i] < arr[r])
    {
        swap(arr[i], arr[r]);
        heapDown(r);
    }
}

The logic here is not optimal for minimum motion. The "lesser" state of the element being pushed down must fall into one of two basic categories, and different actions are taken for each:

1. The element is not less than either left or right. Do nothing.
2. The element is less than either left or right, swap only with the largest, then drive down into only that subtree.

The #2 above in that list is the problem in your code. you swap with the smaller, then the larger, if item < left < right. I hope that is clear. If you want a proposal to fix your logic I can provide one, but I think you may have a handle on it if you understand what I described above.

---

Spoiler

void Heap::heapDown(int i)
{
    int l = left(i);
    int r = right(i);
    int x = 0;

    if (l < n && arr[i] < arr[l])
    {
        x = l;
        if (r < n && arr[l] < arr[r])
            x = r;
    }

    else if (r < n && arr[i] < arr[r])
        x = r;

    if (x != 0)
    {
        swap(arr[i], arr[x]);
        heapDown(x);
    }
}

Note:; In case it wasn't obvious, this is the very definition of tail-recursive, and as such could easily be transformed into a simple iterative loop.