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

[imfatyourefat]

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?

[Momerath]

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.

[imfatyourefat]

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

[jon.kiparsky]

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.

[Rashakil Fol]

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).