Heap Tree - Eishaaya/GMRDataStructuresTest GitHub Wiki

A Different Way to Store Trees

The concept behind a binary heap tree is very simple. There are two types of heaps: min-heaps and max-heaps. In a min-heap, each node must be smaller than either of its children. In a max-heap, each node must be larger than either of its children. With these rules, the minimum or maximum value will always be contained by the root node. The interesting part about heaps is how they are stored. The entire heap tree structure is stored within an array. With math, we can determine the location of the children and the parent of a given index. Here is an example of a min-heap (See if you can extrapolate the equations to determine the left child, right child, and parent of any given index):

Notice that the tree expands in level order. So if we decided to add '5' to the tree, it will end up as a right child of '2'.

Implementation Guide

Insert:

New values will always be added at the end of the array and therefore within row order of the tree (regardless of value). We then HeapifyUp on that node in order to place it into the correct location.

HeapifyUp:

HeapifyUp will compare the value at the given index to its parent and swap them if necessary (the type of comparison depends on if it is a min-heap or a max-heap). This process should continue until the original value cannot be swapped up or the value reaches the root.

Pop:

With heap trees we only care for the root value. So the only way to remove from a heap is to pop the root in a similar fashion to a stack. We don't want to move the next smallest/largest value up immediately though. That could cause gaps in our array and the tree would no longer be filled in row order. So to pop, we place the last value in the array at the root (regardless of value), then HeapifyDown that value until it is inserted into place. Finally returning the original root value at the end.

HeapifyDown:

HeapifyDown will compare the value at the given index to its children's values then swap with the smallest/largest child (depends if it is a min-heap or a max-heap). The process continues until the original value cannot be swapped or the value reaches a leaf position in the tree.

Assignments to be done with a Heap Tree

Heap Sort:

  • Sort a list of random numbers by adding them to a heap then removing them.

References

<-- Previous | Next -->