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