Lecture 23: Projects
& Priority Queues
CS 136: Spring 2024
Katie Keith
Record on Zoom
📣 Announcements
🎯 Today’s Learning Objectives
📚Readings
Final Project Outline
Groups of two!
Tip: Choose a project that you are both excited about
Source: Generated by ChatGPT 4o with the prompt “Create a 3D cartoon image of computer science students being extremely excited, in love, and joyful about their computer science final projects. "
Application possibilities:
Demo #1: Conway's Game of Life on a Torus
Start with a graph structure and then connect it…
A torus structure!
javac -d bin torusGameOfLife/*.java
java -cp bin torusGameOfLife.Panel
The original Conway’s Game of Life Game
Demo #2: Mapping New York City
Excellent example of a thorough README.md
Database of over 850,000 taxplots (roughly corresponding to individual buildings) in NYC and information on each taxplot's location, address, land use type, owner, and more
Final Project Outline
✅
Git/Github workflow
My goal: Help everyone succeed on this final project!
Source: Generated by ChatGPT 4o with the prompt “Create a 3-D cartoon image of a female computer science professor emanating "I’m on your team! Use me as a resource!"
✅
🎯 Today’s Learning Objectives
Assert Statements
assert true == true : "Should never see this message…";
assert true == false : "Bad! True does not equal false.";
An assert statement verifies that a specific condition holds true at a certain point in the execution of a program.
Examples in Java:
reserved keyword
boolean expression we wish to check
message if the boolean expression is false
Using assertions
javac Recurse.java
java -ea Recurse
Assertions in Java are disabled by default at runtime. This is because assertions are typically used during testing and development, rather than production.
To enable assertions, use the -ea command line option at execution time.
Example:
stands for “enable assertions”
✅
✅
🎯 Today’s Learning Objectives
Priority Queues
Priority queues are an ADT that removes the largest (smallest) item using an operation called poll.
Insert
Poll
(Return and remove max element)
Note: Like queues, we can have duplicate items
Where do we use priority queues?
Dijkstra’s algorithm
(Shortest path in weighted graph)
A* search algorithm
(AI pathfinding)
Priority queues are helpful for applications that need to return a max/min value but don’t need the data in full sorted order.
Using a Priority Queue in Java
import java.util.PriorityQueue;
PriorityQueue<Integer> pq = new PriorityQueue<>(); // natural order → minimum is
// highest priority
pq.add(5);
pq.add(2);
pq.add(10);
System.out.println(pq.poll()); // Prints 2 (O(log n))
Data structure next: Binary heap
Can also pass in a Comparator to the constructor to change priority
Complete Binary Tree
Bottom level filled from the left
Heap-ordered complete binary tree
(Max) Heap-ordered complete binary tree:
Note: NOT completely sorted like a Binary Search Tree
4
7
A
B
C
6
6
6
For each of the trees below, choose true/false for the statement “this tree is a heap-ordered complete binary tree”.
💡Think-pair-share
Data structure for Priority Queues: Binary heap
A binary heap is an array representation of a heap-ordered complete binary tree.
Binary heap (array representation):
Index in array
(Max) Heap-ordered complete binary tree:
Properties of Binary Heaps
We begin at index 1 (not 0) because it makes for “easy” arithmetic for parent-child indices
Integer division
Max Binary Heap: Insertion
To insert a node into a binary heap, add the node at the bottom of the tree and swim up (swap a node with its parent whenever the heap order is violated, until the new node is in the correct spot).
Max Binary Heap: poll (return and remove maximum)
To poll (remove the maximum node) in a binary heap, first, exchange root with node at end. Then sink down (swap a node with its the larger of its two child until the heap property holds again).
Note: For min binary heaps, it would be the smaller of the two children
For the tree below,
Array larger than may be needed
💡Think-pair-share
Analysis of Binary Heaps
| insert | poll |
Binary Heaps (Worst case) | O(log n) | O(log n) |
Fast! So we can take advantage of this data structure in other algorithms ⏩
A* search algorithm
(AI pathfinding)
Analysis of Symbol Table’s Data Structures
Data Structure | put | get |
(Unordered) Linked List | O(n) | O(n) |
Two arrays (keys sorted, binary search) | O(n) | O(log n) |
Binary Search Tree | Ave = O(log n) Worst = O(n) | Ave = O(log n) Worst = O(n) |
Hash Table (with separate chaining) | Ave = O(1)* Worst= O(n) | Ave = O(1)* Worst= O(n) |
Hash table (with linear probing) | Ave = O(1)* Worst= O(n) | Ave = O(1)* Worst= O(n) |
*Depends on uniform hashing
Classic time-space tradeoff
If all we care about is poll (max/min), then a binary heap has better worst-case guarantees than symbol tables
✅
✅
✅
✅
🎯 Today’s Learning Objectives