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