2

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 giving 1 as the root node, 100 and 2 and children, 3 and 4 as children of 100 and 5 as a child of 2.

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

Daniel Nill
  • 5,539
  • 10
  • 45
  • 63

1 Answers1

3

The concept you're looking for is "amortized constant time" - i.e. the average is O(1) - even though sometimes there are cases where a single operation takes longer, like in your example above. Take a look at this question for an extended description.

Community
  • 1
  • 1
jwismar
  • 12,164
  • 3
  • 32
  • 44
  • Am I correct in understanding that amortization is application over time? ie if the question is asking for the one time worst case deletion then it should be O(log N)? – Daniel Nill May 08 '11 at 03:48
  • Yes. A single, worst case instance of a deletion in this case would be O(log N). Single instances are in general not considered to be as important as large numbers of instances, because O() notation is most important for large data collections. – jwismar May 08 '11 at 16:58