A Beginner’s Guide to Binary Heaps

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.

3 thoughts on “A Beginner’s Guide to Binary Heaps”

  1. I see you don’t monetize devyashis.me, don’t waste
    your traffic, you can earn additional cash every
    month with new monetization method. This is the best adsense alternative for any type of website (they approve all sites),
    for more info simply search in gooogle: murgrabia’s

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.