Learning Objectives
By the end of this class, you should know...

  • What is a heap?
    • What is the difference between a max and a min heap?
  • What is the heap property of:
    • a max heap?
    • a min heap?
  • How do you build a heap from an unordered array?
  • How do you insert into a heap?
  • How do you sort a heap?
  • What are the Big-O run-times of insertion, sort, and build operations on a heap?

Announcements

Review Activity

With a partner, trace DFS on the following graph:



  • What is the Big-O runtime of BFS and DFS?



Heap Pre-Assessment
  • Below is the representation of a heap.
    • Let's get familiar with heaps and review some important concepts:
  • What does it resemble?
    • A tree?
    • A binary tree?
    • A binary search tree?
    • A balanced tree?
The Heap ADT

What Is a Heap?

  • A Heap is an ADT that is used to represent a Complete Binary Tree (also called an "Almost Complete Binary Tree").
  • Recall from Lesson 9 that a Complete Binary Tree is one where:
    • all levels are filled (except the last)
    • all nodes are as far left as possible
  • For efficiency, the heap data can be stored in an array.


Image source.

Note that a Heap does not satisfy the conditions for a BST.
  • Instead, a heap maintains one of the Heap Properties:
Max Heap Property

A[Parent(i)] >= A[i]

Min Heap Property

A[Parent(i)]  <= A[i]

  • Based on these properties, what kind of heap is the heap above: Max or Min?
  • We will be working with Max Heaps in this class.


Additional Properties of Heaps

  • The images shown above are only representations of a heap that help us to visualize its structure.
  • Like a hash table, the data in a heap is stored in an array.
  • However, consider that a heap is a binary tree that is stored as a linear type (an array).
  • Therefore, a certain ordering must be maintained inside the array:
  1. Root of the heap is at A[1]
  2. Parent of any node A[i]A[floor(i/2)]
  3. left_child of A[i] = A[2i]
  4. right_child A[i] = A[2i + 1]
where i is the index of a node in the array A, with 1 <= i <= size(A)



Verify that these properties are true using the diagram below:




  • Note that the above formulas need to be adjusted if you are indexing your array starting at 0 instead of 1.
  • However, typical heap implementations will simply avoid storing any data in the 0th index of the array.


Applications of Heaps

  • Used for Priority Queue
    • A Priority Queue is similar to the FIFO Queue, but each node also stores a priority value. The first out has highest priority.
  • Sorting algorithm: Heap Sort
    • Will cover at the end of class
  • Selection algorithms:
    • Efficiently find the kth smallest (or largest) element in the array.

Important Heap Algorithms

  • Heapify
  • Build Heap
  • Heap-Insert
  • Heap Sort


Max-Heapify

  • Given a tree which is a valid max heap -- except for node i, the max-heapify algorithm will rearrange node i and its descendants to satisfy the max-heap property.
  • Precondition: left(i) and right(i) are both valid max heaps


  • In other words, we have one value that is out of place. We need to fix the heap!


Max-Heapify Example:

Image source.

  • 4 is out of place. The subtrees at 7 and 8 are both valid max heaps.
  • Swap 4 with its largest child (the right child - 8).
  • Is 4 in the correct position after this swap? No.
  • Swap 4 with its largest child (the left child -6).
  • Is 4 in the correct position after this swap? Yes!


Max-Heapify PseudoCode

Max-Heapify(A, i)

l = left(i) //get the index of the left child of A[i] and store as l

r = right(i) //get the index of the right child of A[i] and store r

//Check if l is off the end of the array (heap) AND compare A[i] to its left child

if (l <= Heap_size(A) AND A[l] > A[i])

    index_of_max = l //update index_of_max if left is bigger

//Check if r is off the end of the array (heap) AND compare A[r] to current max value

if (r <= Heap_size(A) AND A[r] > A[index_of_max]

index_of_max = r //update index_of_max if right is bigger


if (i != index_of_max) //if A[i] was not bigger than its two children

    A[i]<--->A[index_of_max] //swap, so now A[i] stored at A[index_of_max]

    Max-Heapify(A, index_of_max) //recursively move through tree until restore heap property


Run-Time of Max-Heapify: O(height of the tree) = O(log n)


Build-Heap

  • This algorithm takes an un-ordered array and turns it into a valid Heap
  • The build-heap algorithm starts around the middle of the array.
  • It swaps nodes where the parents are smaller than the children (bubbles the values down) until the nodes have reached their correct locations.
    • It uses max-heapify as a helper algorithm to achieve this bubbling down process.
  • The build heap algorithm creates larger and larger valid subheaps until the entire heap is valid.


Build Heap Example

image showing the progression of build max heap algorithm

image source


Build-Heap Pseudocode

Build-Heap(A)

n = Heap_size(A)

for (i = floor(n/2) down to 1) //start at floor(n/2); we can ignore leaf nodes

    Max-Heapify(A, i) //call Max-Heapify helper function


Run-Time of Build-Heap: O(n) (surprise!)

The intuition:
  • The algorithm ignores any leaf nodes (starts at index floor(n/2)).
  • Works bottom up.
    • Every subsequent level requires potentially more swaps,
    • But for only half the number of nodes as the prior level (fewer nodes at each level as you go up the tree)


File:Binary heap bottomup vs topdown.svg

Image source.


Activity: Build Heap Practice

With a partner, trace the build-heap algorithm on the given un-ordered arrays (also below).
  • Call BuildHeap on A= [11, 5, 10, 12, 9, 8, 2, 6, 2, 15]
  • Call BuildHeap on A2 = [12, 7, 15, 9, 2, 4, 6, 8]


Heap-Insert

  • Insert the value at the bottom of the heap, as far left as possible (at the very end of the array).
  • Compare the new key to its parent and swap if necessary.
  • Keep swapping the new key with its parents until the heap property is restored.
  • In other words, the new key "bubbles up" until it reaches its correct location.


Heap Insert Example:

Image source.

  • Assume we begin with a valid Max Heap
  • Insert 441 into the heap (at the very end of the array).
  • Compare 441 with its parent 111.
  • Swap 441 with 111 because 111 is smaller.
  • Now, compare 441 to its new parent 323 and swap because 323 is smaller.
  • Now we have a valid Max Heap again.


The Insertion Algorithm

  • Insertion has two parts:
    • Helper algorithm: Heap-Increase-Key
    • Wrapper algorithm: Heap Insert
  • We will examine both below


Heap-Increase-Key

HeapIncreaseKey(A, i, key)

    if(key > A[i])

        A[i] = key //write over existing value at i with key

    while (i > 1 AND A[Parent(i)] < A[i])

        //while the parent is smaller and you are not at the root node

       A[i] <--> A[Parent(i)] //Swap parent and child

       i = Parent(i) //keep track of current index of the key


Big O Run-Time: O(height of the tree) = O(log n)


Heap-Insert

HeapInsert(A, key)

    A[Heap_size(A)] = –∞ //make space at end of array for new value

   HeapIncreaseKey(A, Heap_size(A), key) //start at the last index, i=Heap_size(A)

    Heap_size(A)++ //we've added a new value to the heap


Big O Run-Time: O(log n)


Group Activity: Heap Insert Practice

  • Insert the values 18 and 10 into each of the heaps from the last exercise.

Heap-Sort

  • Exchange the right most bottom key with the root
  • Rebuild the Heap
  • Repeat
example demonstrating heap sort algorithm


Heap-Sort

HeapSort(A)

    n = length(A)

    for (i = n down to 2)

        A[1] <--> A[i] //swap

        Heap_size(A)-- //consider your heap to be one smaller

        Max-Heapify(A,1) //restore max heap property


Big O Run-Time: O(n log n)


Group Activity: Heap Sort Practice

  • Practice sorting the heaps from the last activities.

Wrap Up

  • With your partner, answer the learning objective questions from the beginning of the lesson.

Upcoming Assignments