CS计算机代考程序代写 python data structure Java algorithm Heaps

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