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:
 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 BigO runtimes of insertion, sort, and build operations on a heap?
Announcements
 Quiz 4 today!
 Project Report 3 due Thursday along with Peer Evaluation 1
 Google E.C.  walk down with us after class and sign in when event is over
 Tomorrow is Veteran's Day Holiday, but I will still be available by email
Review Activity What is the Big O runtime of the hash operations in the best, worst and average cases?
 Rewrite the hash function provided in class
 True or False, a hash function that generates a random index in the table would be a good hash function? Why or why not?
PreAssessment Activity
 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:
 Root of the heap is at A[1]
 Parent of any node A[i] = A[floor(i/2)]
 left_child of A[i] = A[2i]
 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
 HeapInsert
 Heap Sort
MaxHeapify  Given a tree which is a valid max heap  except for node i, the maxheapify algorithm will rearrange node i and its descendants to satisfy the maxheap 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!
MaxHeapify 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!
MaxHeapify PseudoCode MaxHeapify(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
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 the parent was not the bigger one
A[i]<>A[index_of_max] //swap MaxHeapify(A, index_of_max) //restore heap property after performing the swap on subtrees
RunTime of MaxHeapify: O(height of the tree) = O(log n)
BuildHeap  This algorithm takes an unordered array and turns it into a valid Heap
 The buildheap 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 maxheapify 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 source
BuildHeap Pseudocode
BuildHeap(A) n = Heap_size(A) for (i = floor(n/2) down to 1) //start at floor(n/2); we can ignore leaf nodes MaxHeapify(A, i) //call MaxHeapify helper function
RunTime of BuildHeap: O(n) 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)
Image source.
Activity: Build Heap Practice With a partner, trace the buildheap algorithm on the given unordered 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]
HeapInsert  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: HeapIncreaseKey
 Wrapper algorithm: Heap Insert
 We will examine both below
HeapIncreaseKey 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 RunTime: O(height of the tree) = O(log n)
HeapInsert 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 RunTime: O(log n)
Group Activity: Heap Insert Practice  Insert the values 18 and 10 into each of the heaps from the last exercise.
HeapSort  Exchange the right most bottom key with the root
 Rebuild the Heap
 Repeat
HeapSort 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
MaxHeapify(A,1) //restore max heap property
Big O RunTime: 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  Lab 7 due Tuesday
 Project Report 3 due Thursday
