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

• 02-17-2012
c_weed
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?
• 02-17-2012
manasij7479
Quote:

Originally Posted by c_weed
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.
• 02-17-2012
brewbuck
Quote:

Originally Posted by c_weed
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.
• 02-18-2012
c_weed
Quote:

Originally Posted by brewbuck
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?
• 02-18-2012
grumpy
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.
• 02-18-2012
brewbuck
Quote:

Originally Posted by c_weed
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.