Removing elements from heap
- by user193138
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
