What is a Heap?

Heap is a specialized tree-based data structure. There are many different types of heaps. In this article we will be focusing on Binary Heaps.

How it works? In a heap each parent node has up to two children, left child is added first (right or left relationship does-not matter). There is some type of hierarchy (min or max heap).

Types of Binary Heaps:

1. Min Heap: parent nodes are always smaller than (or equal to) the children (right or left sibling order does-not matter)
2. Max Heap: parent nodes are always larger than (or equal to)the children (right or left does-not matter)

Implementation:

Insertion

1. Use a tree: HeapNode Class with a left and right property (fill out from left to right)
2. Array: add the value to the end of the array, and bubble up (compare to parent until it is swapped to the correct spot)

• rightChild = 2(parentIndex)+2
• leftChild = 2(parentIndex)+1
• parentIndex =floor((childIndex -1)/2)

Where do we use Heaps?

Priority Queue (very common): data structure where element has a priority associated with it. (ex. boarding for an airplane, emergency room, unix machines)