https://cs.slides.com/colt_steele/heaps

What is a Binary Heap?

Heap is a tree like structure

• Very similar to a binary search tree, but with some different rules!
• In a MaxBinaryHeap, parent nodes are always larger than child nodes. In a MinBinaryHeap, parent nodes are always smaller than child nodes

This is binary search tree but not a heap

MAX BINARY HEAP

• 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.
• A binary heap is as compact as possible. All the children of each node are as full as they can be and left children are filled out first

A Max Binary Heap

A Min Binary Heap