Binary Heap Trees

Question 1

What is a binary heap ?

Answer 1

A complete binary tree represented as an array,
Max-heap - Every parent node is greater than or equal to its children,
Min-heap - Every parent node is less than or euqal to its children.

Question 2

What is the Insertion operation for a binary heap ?

Answer 2

Insert at the next available spot (bottom layer, left or right),
Swap upwards with the partent until the heap property is restored.
Average: O(1)

Question 3

What is the Deletion opertaion for a binary heap ?

Answer 3

Replace root with the last element,
Swap down with the appropriate child until the heap property is restored.
O(log n)

Question 4

What is the Construction operation for a binary heap ?

Answer 4

Heapify,
Start from the middle of the array and “bubble down”
More effiecient than inserting one at a time.
O(1)

Question 5

How can we impement Binary heaps ?

Answer 5

Using array,
Left child = 2 * i
Right child = 2* i + 1,
Parent = i /2

Question 6

What are the advantages and disadvantages of Binary heaps ?

Answer 6

Advantages:
Fast insertion and deletion,
Ideal for quick min/max access,
Memory efficient,
Foundation for HeapSort.

Disadvantages:
Poort at searching,
Not flexible for other types of operations,
Not stable