Min Heap Idea

Min Heap Idea video (24 minutes) (Spring 2021)

The Priority Queue ADT, which we will see in more detail in later lectures, is a queue in which elements are processed in some priority order. This is different from a standard queue, that has a first-in-first-out processing order.

Priority Queues are often implemented using the Min Heap data structure, which is covered in this lecture.

Array representation of tree (review)

Min Heaps are a type of tree, that can take advantage of the array representation benefits covered in the previous lecture.

Getting the "next" element in a Priority Queue based on Min Heap is O(1) due to array indexing.

Removing from the queue is still O(log(n)), based on the height of a tree having n elements.

Min Heap definition, Max Heap

A Min Heap is a tree that has a less restrictive ordering property than that of a Binary Search Tree. A Min Heap does NOT have the BST ordering property, where a left child is smaller than a node, and a right child is greater.

In a Min Heap, a parent node is simply less than or equal to its child nodes.

This is a valid Min Heap tree. Each node is smaller than its children. It is also a full binary tree.

       B
     /  \
    M     P
  /  \   /
 W   V  X

A Max Heap is the exact opposite of a Min Heap. The same ordering property exists, but in the opposite form. Each node is LARGER than its children.

Heap Operations

The basic operations of a heap are top, push, and pop.

top()

Get the next element to process (in terms of a priority queue), or, the root of the tree. This is simply returning index 0 in the array implementation.

push()

Insert element into the next available spot (bottom right of the tree).

Since the element might not be in the right location (for Min Heap ordering), it will be swapped or percolated UP, with its parent node, until the Min-Heap ordering property is valid again, aka, until it is no longer less than its parent node.

pop()

Remove the root element.

Since we need to maintain a full binary tree, the last element (bottom right of the tree) is swapped up to the root position.

It is then swapped or percolated DOWN the Min Heap, exchanging places with the smaller child, until the Min-Heap ordering property is valid again, aka, until it is no longer great than the smaller child node.

Complexity

push() and pop() are O(log(n)), since they scale in complexity with the height of the tree.

top() is O(1), since it is a simple array access at index 0.

Concept of Priority

In a Heap implementation of Priority Queue, the root node of the heap is the "next in line", or highest priority element.

In a Min Heap, the smallest element is at the root, and thus has highest priority in a Priority Queue based on that Min Heap.

In a Max Heap, the largest element is at the root, and thus has highest priority in a Priority Queue based on that Max Heap.

Min vs Max ordering does not change the concept of priority. It is safe to say that both types of ordering may be encountered "in the wild".

No matter which ordering we use, the highest priority is the root of the heap, for purposes of implementing a Priority Queue with that heap as the underlying data structure.

Thanks

Thanks to Brian Foster for writing up these notes based on the video lectures.