Time complexity to delete a leaf node from Max Heap?

Question

Let's say we're given with a MAX Heap and we want to delete any of the leaf node, then how much time will it take to delete any of the leaf node and maintain the max heap property?

My main doubt is - will it O(n) time to reach to leaf nodes?

Also, why Binary Heaps has to be a complete Binary Tree and not almost complete Binary tree?

Answer 1

A binary heap is a complete binary tree. All levels are full, except possibly the last, which is left-filled. A binary tree is not necessarily a full binary tree.

In a binary heap of size N, represented in an array, the leaf nodes are in the last half of the array. That is, the nodes from N/2 to N-1 are leaf nodes. Deleting the last node (i.e. a[N-1]) is an O(1) operation: all you have to do is remove the node and decrease the size of the heap.

Removing any other leaf node is potentially an O(log n) operation because you have to:

1. Move the last node, a[N-1] to the node that you're deleting.
2. Bubble that item up into the heap, to its proper position.

The first part is, of course, O(1). The second part can require up to log(n) - 1 moves. The average is less than 2, but the worst case is log(n) - 1.