Notes on a Heap

As usual I learned about heaps from two places:

1. Vaidehi's BaseCS
2. Introduction to Algorithms

What's a heap?

• A binary tree
• Parents are always greater than their children (max-heap) OR
• Parents are always smaller than their children (min-heap)

Implementation Notes:

Instead of a node object structure, it's most useful to use a simple array to represent this.

This is because we need:

1. Rapid access to the last element in the heap (which always happens to be the last element in the array)
2. Easy ways to swap the values of two nodes while leaving all their children the same.

So the maths that puts this in order is:

1. For a 0 indexed array
2. The left child of an index is at 2i + 1
3. The right child of an index is at 2i + 2
4. You'd need the equation for the parent but it's best to calculate it from 2*parentIndex + 1 = childIndex to get (childIndex - 1)/2
5. As long as you keep the entire calculation in Int, your language will round it off appropriately whether it's actually the left child or not.
6. Since you'd either end up with a .5 value if it was the right child, which rounds down to the correct parent index, or the actual parent index as an Integer.

Kotlin Implementation

• Easier to use a mutableList and a recursive implementation.
• You'd need to use removeElementAt(size - 1) to get the last value to put at the root.
• I prefer implementing classes that handle generic values, so the MaxHeap takes a T
• However, the type given here has to be a Comparable so that > and < work. So that's the only limitation on the generic value.

Functions:

Insert

• Insert, always bubbles up

Memory Helper: "inserting is positive, going up is positive, they go together"

Extract

• Extract, you'd need to bubble down The root is what you extract, which is the largest or smallest value in the heap. The last element in the heap is then put at the root and bubbled down.

Memory Helper:

"The whole point of the heap is to extract the min/max value and then the value you'd put in there is already at the top so you'd have to go down"

Useful property:

Extracting or inserting always takes LogN time, you can the smallest or largest n elements by calling its extract over and over.

Fun facts:

The book uses 1 indexed arrays and Vaidehi uses 0 indexed arrays, this changes their equations for child nodes.

Code + Test