Case Study · ENSF 338
Campus Navigation System
A Python desktop app that turns a university campus into a live data structure problem. Six custom data structures — AVL tree, min-heap, FIFO queue, circular stack, weighted graph, and HashMap — all implemented from scratch as part of a data structures course.
Overview
What it does
Find the fastest route
Pick any two buildings and Dijkstra's algorithm returns the shortest walking path across the weighted campus graph — instantly, on every query.
Search room bookings
Filter room availability by date and time range. Results come back in chronological order, thanks to an AVL tree's in-order traversal.
Prove O(1) lookup
The fast lookup module doesn't just use a HashMap — it benchmarks it across 7 different sizes and plots the flat curve proving constant time.
No standard library data structures
The priority queue, AVL tree, FIFO queue, and stack are all hand-written Python classes. This was a deliberate constraint — the point wasn't to use the tools, it was to understand them.
Data Structures
Six structures, each with a job
Each structure was chosen because it was the right fit — not because it was easy.
AVL Tree
Room bookings per room
Self-balancing keeps insert and range-query at O(log n) even as bookings pile up. All four rotation cases hand-written.
Min-Heap
Dijkstra's + service desk
The same heap powers both shortest-path and priority service requests — extract-min in O(log n) without any library.
FIFO Queue
Request pipeline
Every GUI action is queued before processing. A moving front pointer keeps dequeue O(1) amortized — no shifting the list on every pop.
Weighted Graph
Campus map
Buildings are nodes, walkways are weighted edges. An adjacency dict makes neighbour lookup O(1) and keeps Dijkstra's implementation clean.
HashMap
Building / room lookup
Python's built-in dict gives O(1) lookup. A benchmark module proves this empirically across sizes from 100 to 100,000 entries.
Circular Buffer Stack
Path history
Fixed-capacity LIFO stack backed by a circular array. Push and pop wrap with modulo — constant time, no resizing.
Algorithm deep dive
How the shortest path works
The campus is an adjacency dict — each building maps to its neighbours with walking times as edge weights. Dijkstra's explores the cheapest unvisited node at each step (via the min-heap), skips stale entries, and reconstructs the path by tracing backwards through a previous dict once the destination is reached.
def dijkstra(self, start_id, end_id):
distances = {bid: float('inf') for bid in self.buildings}
previous = {bid: None for bid in self.buildings}
distances[start_id] = 0
pq = PriorityQueue() # custom min-heap
pq.enqueue((0, start_id))
while not pq.is_empty():
curr_dist, curr_id = pq.dequeue()
if curr_dist > distances[curr_id]:
continue # stale entry — skip
for neighbor_id, weight in self.pathways[curr_id].items():
dist = curr_dist + weight
if dist < distances[neighbor_id]:
distances[neighbor_id] = dist
previous[neighbor_id] = curr_id
pq.enqueue((dist, neighbor_id))
# Walk backwards through previous[] to reconstruct the path
path, current = [], end_id
while current is not None:
path.append(current)
current = previous[current]
path.reverse()
return path, distances[end_id]AVL tree — why balance matters
Room bookings are inserted by (date, time) key. Without balancing, a sorted stream of bookings would degrade a plain BST into a linked list — O(n) per query. The AVL tree's rotations keep the height bounded, so range queries stay fast even with thousands of bookings.
The request pipeline
Every user interaction — finding a path, looking up a room, submitting a service request — is wrapped in a typed Request object and pushed into the FIFO queue. A RequestProcessor dequeues and dispatches each one. The GUI never calls the campus logic directly.
Walkthrough
The app in action
The home screen gives you six entry points. Each one demonstrates a distinct data structure in action — it's as much a learning tool as it is an app.
The map renders the campus as a weighted graph — school buildings in red, other locations in grey, edges labelled with walking times. The selected path (ENG → MAC → TFDL → HNT → HSK, total 14 min) is highlighted above the map after Dijkstra's runs.
60 bookings found across all rooms in a date/time range — returned in chronological order from the AVL tree's in-order traversal.
The right chart is the interesting one — lookup time stays flat as the HashMap grows from 100 to 100,000 entries. O(1) empirically confirmed.
Takeaways
What this built
Algorithms become intuitive
Implementing Dijkstra's on a real graph — not a textbook example — makes the priority queue's role concrete. You stop asking 'why a heap?' and start asking 'what else could you use one for?'
The right structure for the job
Using an AVL tree for time-range queries and a plain HashMap for lookups is an active decision. Building both from scratch means you understand the trade-off, not just the API.
Benchmarking over claiming
The fast lookup module doesn't say 'HashMaps are O(1)' — it proves it with a chart. That habit of measuring rather than assuming carries directly into production work.