1,105,399 Community Members

Deletion in Heap with parent pointers in O(1) time?

Member Avatar
imfatyourefat
Newbie Poster
2 posts since May 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

So here's the question:
Suppose as min heap uses parent pointers such that each node contains a pointer to its parent and the root has a null pointer. Given a pointer to the node, which isn't the root of the tree, containing the max key in the heap, what is the complexity for deletion?

The answer is O(1) but this doesn't make sense to me. Because heaps are always balanced you can't replace the deleted node with an adjacent node you have to scale the length of the tree O(log N) to find the last entered node in the tree, correct? Why isn't the answer to this question O(log N)?

for example:

a heap inserted in order 1, 100, 2, 3, 4, 5

deleting 100 would require replacing it with 5 which takes O(log N) time to access, right?

Member Avatar
Momerath
Senior Poster
3,825 posts since Aug 2010
Reputation Points: 1,323 [?]
Q&As Helped to Solve: 662 [?]
Skill Endorsements: 19 [?]
Featured
 
0
 

If you create your heap with those numbers, you'd end up with 5 as one of the child nodes of 100 so finding it is a O(1) operation.

Member Avatar
imfatyourefat
Newbie Poster
2 posts since May 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

If you create your heap with those numbers, you'd end up with 5 as one of the child nodes of 100 so finding it is a O(1) operation.

sorry for any confusion. The example should be read top to bottom left to right. So 1 is the root and 5 is a child of 2.

1
/ \
100 2
/ \ / \
3 4 5

Member Avatar
jon.kiparsky
Posting Virtuoso
1,837 posts since Jun 2010
Reputation Points: 326 [?]
Q&As Helped to Solve: 192 [?]
Skill Endorsements: 6 [?]
 
0
 

Maybe it's your ASCII art, but that doesn't look like a heap from where I'm sitting. 100 can't be both a child of 1 and a parent of 3.
By the heap property, if the node containing the max element of the tree is not the root, then that node must be in the bottom row - depends on how your heap's structured, but it's one or the other. So as stated, the node to be removed is in the bottom row, and it's a one-step operation to remove it.

Member Avatar
Rashakil Fol
Super Senior Demiposter
2,596 posts since Jun 2005
Reputation Points: 982 [?]
Q&As Helped to Solve: 209 [?]
Skill Endorsements: 42 [?]
Team Colleague
 
0
 

It's a worst case O(log(n)) operation but you can be pretty sure the expected running time is O(1) (given a heap formed from a uniformly selected permutation of an array).

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: