Thread: Basic Heap Question?

if I inserted the numbers :
10,12,1,14,6,5,8,15,3,9,7,4,11,13,2




right?

now what happens if I delete 1...

Practically it depends on how you do it. Well, the common thing would be to delete everything, since deleting a parent node requires deleting everything below, in order to still have a heap.

Dunno, if there is a theoretical answer...

edit: your heap is a min heap. It could have been a max heap with 15 being the root. And, well in your case you want the parent to be <= from the children, so there are other possibilites as well...

http://en.wikipedia.org/wiki/Binary_heap explains how delete of the root works.

--
Mats

Originally Posted by C_ntua

Practically it depends on how you do it. Well, the common thing would be to delete everything, since deleting a parent node requires deleting everything below, in order to still have a heap

That's silly. No it doesn't, that would defeat the purpose of a heap... You just have to maintain the properties of a heap, just sink and rise. Because any child node is also the root of a heap. ie:

Code:

                                                        [   1   ]
                                                    /             \
                                              [  2  ]              [  3  ]
                                           /          \             /        \
                                       [4]          [5]           [ 6 ]      [ 7 ]
                                     /   \         /     \         /   \     /    \
                                   [8]   [9]     [10]   [11]   [12]  [13]  [14] [15]

Hopefully you can see the heaps :-)

Originally Posted by justConfused

if I inserted the numbers :
10,12,1,14,6,5,8,15,3,9,7,4,11,13,2

would my "heap" look like this at the end?

Code:

                                                   [   1   ]
                                               /             \
                                         [  2  ]              [  3  ]
                                      /          \             /        \
                                  [4]          [5]           [ 6 ]      [ 7 ]
                                /   \         /     \         /   \     /    \
                              [8]   [9]     [10]   [11]   [12]  [13]  [14] [15]

right?

Nope. What you've shown in your awesome heap diagram is how the heap would look if you inserted numbers in the order 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, though there are many other insertion orders that would produce the same heap, but that is not one of them. You've actually shown a heap that happens to be in the order that would be sorted in the array. After the first 7 inserts that actual heap would look like this:

Code:

                                                   [   1   ]
                                               /             \
                                         [  6  ]              [  5  ]
                                      /          \           /        \
                                  [14]          [10]       [12]      [ 8 ]

now what happens if I delete 1...

Then the rightmost bottom node would be moved to its place and then the reheapify operation occurs.