Basic Heap Question?

This is a discussion on Basic Heap Question? within the C Programming forums, part of the General Programming Boards category; 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......

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    2

    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...
    Last edited by justConfused; 12-02-2008 at 09:58 PM.

  2. #2
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    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...
    Last edited by C_ntua; 12-02-2008 at 03:18 AM.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    http://en.wikipedia.org/wiki/Binary_heap explains how delete of the root works.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Quote 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 :-)
    Last edited by zacs7; 12-02-2008 at 03:29 AM.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by justConfused View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A basic math programming question
    By hebali in forum C Programming
    Replies: 38
    Last Post: 02-25-2008, 03:18 PM
  2. Basic question about GSL ODE func RK4
    By cosmich in forum Game Programming
    Replies: 1
    Last Post: 05-07-2007, 02:27 AM
  3. Basic question about RK4
    By cosmich in forum C++ Programming
    Replies: 0
    Last Post: 05-07-2007, 02:24 AM
  4. Basic C question ---- URGENT
    By x135 in forum Linux Programming
    Replies: 3
    Last Post: 03-25-2006, 10:05 PM
  5. A very basic question
    By AshFooYoung in forum C Programming
    Replies: 8
    Last Post: 10-07-2001, 03:37 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21