Introduction to Binary Heaps
Today, we will discuss a binary heaps, a common data structure in programming. Heaps have multiple uses in programming including:
- Priority Queues: a queue-like data structure which has a priority field as a key. In a priority queue implemented with a min-heap, the element with the lowest value for priority will the next available element. In a priority queue implemented with a max-heap, the element with the highest value for priority will be the next available element.
- Finding the k’th [small/larg]est element: Heaps are really good at solving this problem, because after creating a heap from the target elements, the lowest (min-heap implementation) or the highest (max-heap implementation) values can be extracted with ease.
Heaps are very useful when you need to retrieve the max (max-heap) or min (min-heap) quickly (\(O(\log n)\)), need to add an element with a certain value quickly (\(O(\log n)\)), and need to be able to build the structure quickly (\(O(\log n)\)).