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

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 sens开发者_StackOverflow中文版e 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?

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.