A heap is a special type of tree with two properties.

1. The first property of a heap is that it should be a Complete tree which means every level, except potentially the last level, is completely filled, and levels are filled from the left to the right.
2. The second property of a heap is that the value of every node is greater than or equal to its children. This is called the heap property.
3. Max heap: the root node holds the largest value, and as we go down in the tree, values get smaller.
4. Min heap: where the root node stores the smallest value and as we go down in the tree, values get larger.

Heaps Applications

• Sorting (HeapSort): We can use them for sorting data
• Graph algorithms (shortest path): To find the shortest path between two nodes in a graph. This is the algorithm that powers your GPS.
• Priority queues
• **Finding the Kth smallest/largest value @**This is a very popular interview question

Runtime complexity

The longest a value can travel is equal to the height of the tree. This is similar to finding a value in a binary search tree. In a binary search tree, if you want to find a value, we start from the root and travel down the height of the tree until we get to a leaf node.

Bubbling up an item is the same in terms of the number of comparisons we need, but it happens in the opposite direction.

$$ h=log(n) $$

$$ O(log n) $$

Deletion: In heaps, we can only delete the root node, not one of the inner nodes. And we have to bubble down the heap by until it a Complete tree.

Removing the largest value: In a heap also runs in logarithmic time.