- Sat, Sep 2nd, 2023
- Heap
- Exercise: Convert aBalanced_Tree into a Min heap.
- Keep doingsift_down starting from the last element and then keep going up.
- heapify min heapify, compare the left element of root node and then the right element with the root node.
- minheapify time complexity is log(n)
- there is a loop so total complexity for making balanced tree to Heap is n log(n)
- 2^h - 1
- The time complexity is decided the height of the tree and the height of most subtree is usually small.
- Upper bound??
- Tree height goes in log n series.
- There is an equation
- Priority Queue