Programming Help

Web Development

Projects



What's Here?

  • Members: 86,242
  • Replies: 356,462
  • Topics: 52,265
  • Snippets: 1,779
  • Tutorials: 422
  • Total Online: 2,259
  • Members: 68
  • Guests: 2,191

Who's Online?

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

Join 86,242 Programmers. There are 2,259 online right now! Ask your question and get quick answers from Dream.In.Code experts. Join the #1 programming help community on the internet! Registration is fast and FREE... Join Now!

Chat LIVE With a Expert
Powered by LivePerson.com

Register to Make This Box Go Away!

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


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
+Quote Post


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


2B||!2B

Group Icon
Joined: 18 Feb, 2007
Posts: 2,022
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
+Quote Post

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


New D.I.C Head

*
Joined: 12 May, 2008
Posts: 5
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
+Quote Post

Fast ReplyReply to this topicStart new topic
Time is now: 5/16/08 08:20AM
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