In a heap can a node that's not the root be removed?

This is a discussion on In a heap can a node that's not the root be removed? within the Tech Board forums, part of the Community Boards category; In a heap can the node that's not the root be removed? For example in this diagram How would node ...

  1. #1
    Registered User
    Join Date
    Apr 2010
    Location
    Vancouver
    Posts
    122

    In a heap can a node that's not the root be removed?

    In a heap can the node that's not the root be removed? For example in this diagram How would node with key 25 be removed?

  2. #2
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by c_weed View Post
    In a heap can the node that's not the root be removed? For example in this diagram How would node with key 25 be removed?
    (AFAIK) Not efficiently if the heap is represented in an array.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  3. #3
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,248
    Quote Originally Posted by c_weed View Post
    In a heap can the node that's not the root be removed? For example in this diagram How would node with key 25 be removed?
    I'm assuming you are using the array representation of the heap.

    Removing an arbitrary node is no different than removing the root node. Just replace the node with the last element of the heap (last element in the array), then do a heapify-down operation to preserve the heap property.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  4. #4
    Registered User
    Join Date
    Apr 2010
    Location
    Vancouver
    Posts
    122
    Quote Originally Posted by brewbuck View Post
    I'm assuming you are using the array representation of the heap.

    Removing an arbitrary node is no different than removing the root node. Just replace the node with the last element of the heap (last element in the array), then do a heapify-down operation to preserve the heap property.
    Replace with last element in entire heap or last child of removed node?

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,425
    In principle, any node can be removed from a heap, including even the root node.

    The efficiency of that operation, and the steps needed to maintain integrity of the heap, are the costs of doing that.
    Right 98% of the time, and don't care about the other 3%.

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,248
    Quote Originally Posted by c_weed View Post
    Replace with last element in entire heap or last child of removed node?
    You'd replace the node you are removing with the last element in the heap. And upon thinking more about it, I think you need to heapify up as well as down to preserve the heap property. I think grumpy's implication that it might be more expensive than removing the root is probably correct.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. root in managed heap
    By George2 in forum C# Programming
    Replies: 0
    Last Post: 04-20-2008, 12:59 AM
  2. deleting arbitrary node from a heap
    By DavidP in forum C Programming
    Replies: 4
    Last Post: 02-10-2008, 10:47 PM
  3. Replies: 5
    Last Post: 11-17-2007, 02:47 PM
  4. Cutting a heap at a given node
    By kris.c in forum C Programming
    Replies: 13
    Last Post: 07-21-2007, 09:12 AM
  5. Replies: 5
    Last Post: 10-04-2001, 03:42 PM

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