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.

2. Heap-Sort

• Exchange the right most bottom key with the root (swap)
• Rebuild the Heap (heapify)
• Repeat

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):

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! ~