Heaps + Linked List + deletion + leaf

[xyster]

Hello all,

I have been a member here for some time, i must admit this is my first post. I have read the posting rules, lets hope my title is considered "meaningful".

i have no code snippet, yet. I have just hit a sudden wall in my heap programming.

I have created a min heap.

The way i was taught to remove the min value from a heap was to remove the root and replace it with the bottom right most leaf. (i think, it was quite some time ago).

so, like this; http://www.ces.clemson.edu/~warner/M865/HeapDelete.html

however, i can't seem to get my head around finding the leaf in my heap.

once you do this you simply heapify correct?

I am looking for a bit of pseudo code or a word example, if possible.

- Thank you in advance for any and all help
- xyster
P.S: sorry if i have failed in the posting, i have searched the forum. i chose not to add my own code as i didnt believe it was relevant here, but i will post what i am using if needed.

P.P.S: my struct for my heap has a parent, left, right and a data point for comparison of importance.

[Nick Evan]

Here's a great tutorial with some example code. (scroll down to heap)

[xyster]

i read through that entire piece. It does use arrays, i managed to make some sense of it all, but i still dont see how it finds the bottom right most leaf in a heap to replace the root with when getting the min value of the heap.

Thank you for the sample code, it did help refresh my memory on heaps though.