# Binary Heap

A binary heap can be used as a priority queue, as the highest (or lowest) value node is always at the root of the tree.

## Types of Heaps

### max-heap

The value of each node is greater than all of its descendants

### min-heap

The value of each node is less than all of its descendants

## Heap Rules

Follow its heap condition (either max-heap or min-heap)

The tree must be complete

It must not have any empty node positions. Although the bottom row can have empty positions. But there cannot be any nodes to the right of those empty nodes.

Example of incomplete heap (the 36 does not have a left child)

## Heap properties

Heaps are weakly ordered.

It's not ordered like a binary search tree where values less than a node are on the left branch, and values greater than the node are on the right branch.

We only know that the descendant nodes are smaller than a given node in a max-heap. And vice versa for a min-heap.

In a max-heap, the greatest value will always be at the root node. In a min-heap the smallest value will be at the root node.

## Implementation

Heaps are usually implemented as an array. This makes it easy to keep track of the root node and the last node in the 'tree'. The root node is the first element of the array. The last node is the last element of the array.

The first two diagrams above show how the heap is represented in the array.

To find the left child of a node:

(index * 2) + 1

To find the right child of a node:

(index * 2) + 2

To find the parent of a node:

(index - 1) / 2

Note: the above does integer division, so the remainder is thrown away

## Primary Operations

### Insertion

These steps are for a max-heap. Min-heap follows the same steps except a min comparison is done instead.

A new node is inserted into the last node

The new node is compared to its parent node

If the new node is greater than its parent, swap the nodes

repeat steps 2 - 3 until it has a parent that has a greater value than it.

### Deletion

These steps are for a max-heap. Min-heap follows the same steps except a min comparison is done instead.

**Important:** We only ever delete the root node.

Replace the root node with the last node

Trickle the root node down to its proper place

Check both children of the trickle down node to see which one is bigger

If the trickle node is smaller than the larger of the two child nodes, then swap the trickle node with the larger child

repeat above two steps until the trickle node has no descendants that have a greater value than it

By repeatedly popping the root element, we get the list in sorted order (descending). It will be in ascending order for a min-heap.

Last updated