Nerd For Tech
Published in

Nerd For Tech

Learning Binary Heaps

A heap of trash

Up until this week, the only heaps I was familiar with were the heaps of trash that are a mainstay of NYC streets. Thankfully this week of studying data structures has shown me that not all heaps are hot garbage. In this article, I will be reviewing what I have learned so far about binary heaps as well as how to construct and interact with them. A lot of the images in this article are from my repl, where I constructed a Max Binary Heap and wrote a few class methods to make it functional. I also have some notes in there that will cover much of this article. I hope that both can be helpful to anyone who is interested on gaining a basic understanding of how binary heaps work.

Heaps are a type of tree. They are a lot like Binary Search Trees, but have their own unique logic, rules, and use cases. If you are not familiar with Binary Search Trees(BST), please check out my articles on BSTs and Tree Traversal. Just like in a BST, each node in a binary heap has at most two children(hence them sharing the binary in their name).

However, the rules around the order of nodes is very different. There are two main types of binary heaps, Max Binary Heaps(Max Heap), and Min Binary Heaps(Min Heap). In a Max Heap, each node’s children must have a lower value than their parents. This means that the root node will always have the highest value in the heap. In a Min Heap, the opposite is true. The root node always has the lowest value, and each child node must have a greater value than its parent. Another difference between binary heaps and BSTs aside from the rules I just outlined is that there is no inherent left to right order ascending order for the value of nodes. You can not infer anything about the value of a node’s sibling other than it is also lesser or greater than their parent, depending on if it is a Max Heap or a Min Heap.

What may be the most important between a binary heap and a BST is that the left child node will always be assigned before the right one, and each node must have two children before another level can be added to the heap. This is a stark departure from BSTs, where one could theoretically keep adding nodes to only the left side or the right side, making it look more like a linked list. This difference is essential to a lot of the logic that you will see in my code screenshots below. We are able to construct a heap using an array because of this difference, since with a little bit of math we can figure out the index of a parent node based on it’s child’s index. Given an index of ‘x’, we can call Math.floor of (x — 1)/2. If x is the left child, it will divide evenly by 2. If x is the right child, it will be a float, such as 2.5, and then we can round it down.

Below are some screenshots of the Max Heap that I constructed on replit. This heap is capable of adding a new node or removing the root, and re-organizing the heap. It requires very little set up, since the Heap itself just needs an array of node values to work.

I hope that this has been informative and interesting! Next time, I will be writing about priority queues, which also use heaps.

--

--

--

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.

Recommended from Medium

What is the scope of Front-end Developers?

Networking 101 GCP reference sheet

networking 101

Dell Boomi Integration: User Guide

A dive into KeplerSwap Tokenomics

Day 13 — Getting started with Coroutines in Unity

Audit Results & Launch Plan

If Programming Languages Were Never Have I Ever Characters

Thibaud explains… Bash#1 — ls *.c

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Liam Hanafee-Areces

Liam Hanafee-Areces

More from Medium

Big-O Notation

Check if the parenthesis/brackets in a string are balanced or not. Python and stack Data Structures

Algorithms, my attempt to write and understand binary search