#self_doubt

Question

what if a full binary tree contains both left and right sides as the max heap, then what will be the complexity of making it a proper max heap?

Comments

it should be $O(logn)$,

as in worst case we can have the minimum element at the root, so performing max heapify procedure once we can get the desired max heap.

---

but it is a full binary tree, not a complete binary tree.

---

Dknights

A full binary tree with both left and right ST’s as max heap.

Answer 1

A full binary tree is a binary tree in which every node has either 0 or 2 children. If a full binary tree contains both left and right sides as max heap, then the time complexity of making it a proper max heap will be O(n) where n is the number of nodes in the tree.

This is because in a full binary tree, each node has two children, and to convert it into a proper max heap, we need to compare the value of each node with its children, swap it if necessary and repeat the process for all the nodes in the tree. Since each node has two children, and the tree is full, we have to repeat this process n times, and hence the time complexity is O(n).

Answer 2

if a full binary tree contains both left and right sides as the max heap, then the worst-case time complexity of making it a proper max heap is O(log(n)). As the left sub-tree, as well as the right sub-tree, are heaps then I assume they are complete in the worst case.