Welcome to Lesson 19!

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

  • How do you insert into a heap?
  • How do you sort a heap?
  • What are the Big-O run-times of insertion and sort operations on a heap?

1. 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.


1.1. 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)
    Heap_size(A)++ //adding a new value to the heap

    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)

   
Big O Run-Time: O(log n)


1.2. Group Activity: Heap Insert Practice

  • Insert the values 18 and 13 into the heap from the last exercise.
The heap from the last exercise

2. Heap-Sort

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


2.1. Heap-Sort

HeapSort(A)

    n = Heap_size(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)


Example of one iteration of heap-sort (swap and heapify):


Wszystko, co chciałeś wiedzieć o algorytmach sortujących ...


2.2. Group Activity: Heap Sort Practice

  • Trace heap sort on the following heap: [10, 9, 8, 6, 5, 4]

Wrap Up
  • Answer the review questions for this lesson on Canvas

~ Have a Great Day! ~