Binary Heaps

Question 1

how to construct an array backed min heap, without using buildHeap()

Answer 1

for every item in the array call add() method, which results in O(nlogn) method, becasue each add costs O(logn)

Question 2

given data at index n for a binary heap,
- what’s its left child’s index
- what’s its right child’s index
- what’s its parent’s index

Answer 2

• what’s its left child’s index: 2n
• what’s its right child’s index: 2n + 1
• what’s its parent’s index: n/2

Question 3

how does buildHeap( ) work and what’s its time complexity

Answer 3

use recursion to build valid subheaps incrementally that eventually assemble into the complete heap
1. loop from size/2 to 1
2. call the method itself to determine if a swap between the parent and any of its children is needed

time compelxity is O(n)

Question 4

how does add work in a heap

Answer 4

1. add to the back of the array
2. perform up-heap

Question 5

how does remove work in a heap

Answer 5

1. move the last element to replace the root
2. perform down-heap