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 Big-O run-times of insertion, sort, and build operations on a heap?
Announcements
Review Activity
With a partner, trace DFS on the following graph:
- What is the Big-O runtime of BFS and DFS?
Heap Pre-Assessment
- 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
- Heap-Insert
- Heap Sort
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!
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!
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
Run-Time of Max-Heapify: O(height of the tree) = O(log n)
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.
Build Heap Example image source
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
Run-Time of Build-Heap: O(n) (surprise!)
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 build-heap algorithm on the given un-ordered 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]
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.
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) 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 Run-Time: O(log n)
Group Activity: Heap Insert Practice - Insert the values 18 and 10 into each of the heaps from the last exercise.
Heap-Sort - Exchange the right most bottom key with the root
- Rebuild the Heap
- Repeat
Heap-Sort 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
Max-Heapify(A,1) //restore max heap property
Big O Run-Time: 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 |