Nerd For Tech
Published in

Nerd For Tech

Binary Heaps

A binary heap is a type of binary tree that has its own set of rules. There are two types of binary heaps which are the max-heap and the min-heap.

Rules

The first rule the binary max-heap follows is that each node’s value must be greater than the value of all of its descendants. This means that if the node you are looking at is an 8 all following nodes must be less than 8. In a binary min-heap, each node’s value must be less than the value of all of its descendants. As you can see the rule is reversed depending on the type of binary heap you create.

Example of a Binary Max-Heap

The second rule is that a binary heap must be a complete tree. A complete tree is one that is completely filled with nodes. This means that when reading the tree left to right all nodes are there. The exception to this is that nodes on the bottom row can be missing as long as no nodes are to the right of the empty node.

To the left is an example of a complete tree missing nodes in the bottom row. To the right is an example of an incomplete tree because there are nodes to the right of the empty nodes.

Insertion

To insert a value, we create a new node and place it at the rightmost spot on the bottom level of the heap. In a max-heap, we will compare the new node with its parent and swap them if the new node is greater than the parent. This will be repeated until the new value gets a parent that is greater than itself or it is the new root node. For a min-heap it is the same process except you will be switching the values if the new node is less than the parent.

Insert 45 in a max-heap

The square here represents the rightmost spot. We will compare 45 with its parent 12. 45 is greater than 12 so we will swap them.

Again compare 45 with its new parent 33. 45 is greater than 33 so we will switch them.

Lastly, we will compare 45 with its new parent 50. 50 is greater than 45 so we know that 45 is in the correct position.

Deletion

When deleting from a binary heap we will only ever delete the root node. To delete we will move the last node to the root node. This will delete the original value of the root node. If you are using a max-heap you will then compare the value of the parent with its children and swap it with the greater of the two values. This will continue until the node is in the correct spot. With a min-heap, it is the same except the parent will swap with the smallest of the two values.

Delete 50 from the max-heap

First, replace 50 with the last node in the heap.

The square is showing that that is the position the 12 came from as it was the last node in the heap.

Next, compare 12 with its children 45 and 25. We will swap 12 with 45 because it is the greater value between the two children.

Now compare 12 with its new children 20 and 33. 33 is the greatest value so we will swap 33 and 12.

We are now done because the 12 has no more children.

Use Case

A binary heap is a great option for implementing a priority queue. A priority queue is similar to a regular queue where deletion and access are the same. The difference is that the values are inserted in a specific order. A perfect example of a priority queue is the triage system used in emergency rooms. When a patient comes into the emergency room the severity of their condition is evaluated and they are added to the queue based on this. This allows the hospital to treat patients in a worse condition first. The binary heap works well for this as the root will always be the highest priority patient.

For more on the implementation of the binary heap check out this article by GeeksforGeeks.

--

--

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