Verify that these properties are true using the diagram below:

Node: 53 Index:

Node’s Parent: Parent’s Index:

Node: 59 Index:

Left Child: Left Child’s Index:

Right Child: Right Child’s Index:

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

**2.5. 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 heap lesson

- Selection algorithms:

- Efficiently find the kth smallest (or largest) element in the array.

**2.6. Important Heap Algorithms**

- Heapify
- Build Heap
- Heap-Insert

- Heap Sort

**3. 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!

**3.1. 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!

**3.2. 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

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

**4. 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.

**4.1. Build Heap Example**

*image source*

**4.2. 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

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

*The intuition: *