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)\)).

Binary heaps are a data structure with two important properties:

• Nearly Complete: every level of the tree is filled, except the last level, which can be partially filled from left to right.
• In a min-heap, a child cannot be smaller than its parent; in a max-heap, a child cannot be larger than its parent.

Because of the second property, in a max-heap, the root node is the largest value; in a max-heap, it is the smallest value.

• Below is a proper max-heap. Note that no child is greater than its parent?:
• Below is a proper min-heap. Note that no child is smaller than its parent?:
• What is wrong with the tree below? 
  • It is not nearly-complete. To be nearly complete, every row must be filled from top to the bottom, except the last row, which must be filled from left to right until full.
  • In order for a tree to be nearly complete, every row except the last must be completely filled. The last row should be filled from left to right.
  • In this example, the bottom row is not filled from left to right.
• Why is the following tree not a heap?
  • This tree does not conform with the min-heap property that every child should be larger than its parent. In this case, 8 is less than 10, so it fails.