Programming Help

Web Development



What's Here?

  • Members: 105,410
  • Replies: 403,642
  • Topics: 61,195
  • Snippets: 2,206
  • Tutorials: 596
  • Total Online: 1,748
  • Members: 77
  • Guests: 1,671

Who's Online?

Welcome to Dream.In.Code
Getting Help is Easy!

Join 105,410 Programmers for FREE! Ask your question and get quick answers from experts. There are 1,748 online right now! We've got more than 500 tutorials and 2,000 snippets. Join and find out why Dream.In.Code is the #1 programming help community on the internet! Registration is fast and FREE... Join Now!



Heaps

 
 Reply to this topicStart new topic

Heaps
Irishancest
post 6 Apr, 2008 - 09:36 PM
Post #1


New D.I.C Head

*
Joined: 2 Nov, 2007
Posts: 14


My Contributions
I have a max heap where i am deleting and the root's children are the same number. Does it matter which is replaced.

36
/\
34 34

The 36 is deleted, is it replaced with left or right?
User is offlineProfile CardPM

Go to the top of the page


NickDMax
post 7 Apr, 2008 - 01:34 PM
Post #2


2B||!2B

Group Icon
Joined: 18 Feb, 2007
Posts: 2,664



Thanked 26 times

Dream Kudos: 475
My Contributions
Well from what I remember you have to have the left child if there is a child. But in the situation you pose there no difference.

I think a better explanation requires that we know just what KIND of heap you are using. I mean just a HEAP does not make any rules for what is stored where, so I would assume that you would take the right most node and just replace it would the current node.

but in a min heap you will replace the root node with the min value. If there exists more than one it makes no difference which you choose.
User is offlineProfile CardPM

Go to the top of the page

cutegrrl
post 13 May, 2008 - 03:57 AM
Post #3


D.I.C Head

**
Joined: 12 May, 2008
Posts: 72



Thanked 7 times
My Contributions
By definition, a heap follows the form of a complete binary tree, that is, every level but the last must have the maximum number of nodes possible at that level, and at the last level, the nodes should be arranged from left to right without any empty spots. Thus when deleting from a heap, we remove the rightmost node in the last level. In your case, the right child, replaces 36.

This same procedure is followed in larger heaps. The only difference is that after the rightmost node in the last level replaces the root, the node is 'sifted down' such that the heap ordering is maintained.

This post has been edited by cutegrrl: 13 May, 2008 - 04:04 AM
User is offlineProfile CardPM

Go to the top of the page

Fast ReplyReply to this topicStart new topic
Time is now: 8/20/08 05:23AM
Invision Power Board v2.1.7 © 2008  IPS, Inc.
Licensed to: MediaGroup1

Live Help!

Tutorials

Programming

Web Development

Reference Sheets

Code Snippets

Bye Bye Ads

Free DIC T-Shirt

T-Shirt Example

Related Sites

Monthly Drawing

Thumb Drive

Partners

Top Contributors

Top 10 Kudos This Month