OBJECTIVES
- Define what a binary heap is
- Compare and contrast min and max heaps
- Understand where heaps are used in the real world and what other data structures can be constructed from heaps
What is a Binary Heap
The binary heap is much similar to the binary tree with slightly different rules.
The Binary Heap is divided into two which are
- MaxBinaryHeap
- MinBinaryHeap
MaxBinaryHeap Points
- Each parent has at most two child nodes
- The value of each parent node is always greater than its child nodes
- In a max Binary Heap, the parent is greater than the children, but there are no guarantees between sibling nodes.
MinBinaryHeap Points
- Each parent has at most two child nodes
- The value of each parent node is always smaller than its child nodes
- In a min Binary Heap, the parent is smaller than the children, but there are no guarantees between sibling nodes.
BigO of Binary Heap
Insertion – O(log N)
Removal – O(log N)
Search – O(N)
Uses of Binary Heaps
- Binary Heaps are used to implementing Priority Queues, which are very commonly used data structures
- They are also used quite a bit, with graph traversal algorithms.
What is a Priority Queue
A data structure where each element has a priority. Elements with higher priorities are served before elements with lower priorities.
RECAP
- Binary Heaps are very useful data structures for sorting and implementing other data structures like priority queues
- Binary Heaps are either MaxBinaryHeaps or MinBinaryHeaps with parents either being smaller or larger than their children
Written by: Ebube Okocha