Heaps
CSC263 Week 2
The course slides, worksheets, and modules
are based on the CSC263 Winter 2021
offering and were developed by Michelle Craig
(with some help from Samar Sabie)
Announcements
• Recognized Study Groups (RSG)
• Piazza signup
• Academic Integrity Reminder
• Quercus Due Day Temporary Change
• Quercus Week 2 Module due May 13 at 2pm
• Considering an extension to May 16
uoft.me/recognizedstudygroups
Develop your leadership and facilitation
skills while learning course materials.
Leader Applications Open April 20
Lead or
Join a
Recognized
Study
Group Study with your classmates, make new friends
and stay focused while studying online.
Sign Up to Join Starting May 10
Designing a Data Structure for Priority Queue ADT
Data
A collection of items
which each have a
priority
Operations
Insert(PQ, x, priority)
FindMax(PQ)
ExtractMax(PQ)
IN(8), IN(5), IN(10), IN(3), FM(), IN(16), EM(), EM(), IN(7)
Example sequence used across various implementations:
Approach 0: An unsorted linked list
Discussed in DISCOVER module
Insert in O(1)
FindMax in O(n)
ExtractMax in O(n)
Approach 1: An unsorted Array
IN(8), IN(5), IN (10), IN (3), FM(), IN(16), EM(), EM(), IN(7)
Chalk Talk
Important Side Note
• Both Python and Java often hide the complexity of operations
• Appending an element into a Python list
L.append(x)
In this course we want to write and analyze algorithms from the simple
operations that don’t depend on hidden complexity.
Approach 1: An unsorted Array
IN(8), IN(5), IN(10), IN (3), FM(), IN(16), EM(), EM(), IN(7)
Size
Chalk Talk
Approach 2: A Sorted Array
IN(8), IN(5), IN(10), IN(3), || FM(), IN(16), EM(), EM(), IN(7)
Size
Chak Talk
What if we kept the items in the array in sorted order?
10 8 5 3 4
Approach 3: An Ordered Linked List
IN(8), IN(5), IN(10), IN(3), FM(), IN(16), EM(), EM(), IN(7)
Worksheet Q1-4
What if we kept the items in an ordered linked list?
Approach 4: A Binary Search Tree
IN(8), IN(5), IN(10), IN(3), FM(), IN(16), EM(), EM(), IN(7)
Worksheet Q1-4
What if we kept the items in a binary search tree?
Heaps
• Based on a nearly complete binary tree
• Heap Property determines relationship between values of parents
and children
• Kind of sorted: enough to make query operations fast while
not requiring full sorting after each update.
• Stored in an array
Nearly Complete Binary Tree
• Binary tree
• Every row is completely filled except possibly the lowest row
• The lowest row is filled from the left
Heap Property
• Max Heap
The value at every node is equal to or greater than the value of its
immediate children
• Min Heap (you fill this one in)
Is this a valid heap?
Zoom reaction activity
Is this a valid heap?
Zoom reaction activity
Is this a valid heap?
Zoom reaction activity
Is this a valid heap?
Zoom reaction activity
Is this a valid heap?
Zoom reaction activity
Is this a valid heap?
Zoom reaction activity
Implementing the PQ Operations: Insert
• Increment heapsize and add element at next position
• Result might violate heap property so _____________
• Running time? __________________
Insert(13)
Chalk Talk
Implementing the PQ Operations: FindMax
• Doesn’t change heap
• Running time?
Findmax()
Chalk Talk
Implementing the PQ Operations: ExtractMax
• Remove and return root element
• Strategy: restore shape first then fix heap property
• Bubble down also called ________________________
• Running time? ________________________
Chalk Talk
Now the really cool bit!!!
• Use an array to store the heap (not linked nodes and
references)
• Convention: use 1-based indexing so root is at element 1
• For node at position i, left child is at____, right child is at
____, and parent is at ____.
Is this a valid heap?
Zoom reaction activity
A = [17, 12, 2, 5, 8]
Is this a valid heap?
Zoom reaction activity
A = [17, 12, 2, 5, 8, 0, 0, 0] heapsize=5
Is this a valid heap?
Zoom reaction activity
A = [17, 12, 2, 5, 8, 18, 0, 72] heapsize=5
Heap Sort
Assuming we start with a valid heap, how do we get a sorted list?
Notice that the root of the heap stores the maximum element
KEY IDEA
• Remove the root and put it in an array at the end
• Decrement heapsize
• Restore the heap property
2nd KEY IDEA
• Do this in place since replacement item for root was in the position where we
want to put the root anyway.
Heap SortChalk Talk
1 2 30 4 5 6 7 8 9 10 11
Going from a Max Heap to a listed sorted in non-decreasing order:
Heap SortChalk Talk
1 2 30 4 5 6 7 8 9 10 11
Going from a Max Heap to a listed sorted in non-decreasing order:
Heap SortChalk Talk
1 2 30 4 5 6 7 8 9 10 11
Going from a Max Heap to a listed sorted in non-decreasing order:
Heap SortChalk Talk
1 2 30 4 5 6 7 8 9 10 11
Going from a Max Heap to a listed sorted in non-decreasing order:
Bubble-down or Max-Heapify
def maxHeapify(L, i):
1 l = left(i)
2 r = right(i)
3 if l <= L.heapsize and L[l] > L[i]:
4 largest = l
5 else:
6 largest = i
7 if r <= L.heapsize and L[r] > L[largest]:
8 largest = r
9 if largest != i:
10 exchange L[i] with L[largest]
11 maxHeapify(L, largest)
Building a Heap in the First Place
• Our discussion of heap sort only talked about going from a valid
heap to a sorted list.
• But typically, we want sorting algorithms to go from an unsorted list
to a sorted list.
• So, how do we efficiently go from an unsorted list to a valid heap?
Building a Heap in the First Place
• Complete Q5 and Q6 in this week’s worksheet
• Put your results into the Google Doc for your breakout group
https://tinyurl.com/csc2635
• If you are working alone (watching the videos later), stop the video
and give yourself 10 minutes to do the exercise and write down your
answers.
• Iff you have finished Q5 and Q6, go on to Q7
Worksheet
https://tinyurl.com/csc2635
Runtime of Building a Heap
• Using the second approach we make O(n) calls to Max-Heapify and
each one takes O(log n), so we immediately get a bound of O(n log n)
but we can do better!
Chalk Talk
Runtime of Building a Heap
• So how many subtrees of each height do we have?
More Space for Chalk Talk
Runtime of Building a Heap
Gabriel’s Staircase Series:
More Space for Chalk Talk