Priority Queue · Data Structures and Algorithms

Priority Queue

CSC-211 · Semester III · Data Structures and Algorithms

intermediate25 minAvailable

Priority queueSorted by priority · min first

42p = 2

17p = 5

90p = 1

33p = 3

extract order (smallest p first)

Next out

(42, p=2)

Lab brief

Objective

Observe a priority queue where the highest-priority element is always served first, regardless of arrival order.

Theory & concepts

A priority queue removes elements by priority, not by arrival order. Each item carries a priority; the next dequeue always returns the item with the smallest (or largest) priority value. A naive implementation scans the whole queue each time (O(n) per dequeue), which is why real priority queues are usually built on binary heaps for O(log n) operations.

Rendering diagram…

Priority queue service order

enqueue(item, p)  → insert by priority
highest priority  → served first (min-priority queue)
dequeue           → remove the most urgent item
Naive scan        → O(n); heap implementation → O(log n)

Prerequisites

Lab: Circular Queue
Comparison of numeric values

Instructions

1Enqueue items with different priorities in scrambled order.
2Dequeue and watch the highest-priority item leave first each time.
3Add an item with the most urgent priority mid-simulation and see it jump the queue.
4Tie-break: observe how equal priorities are served.

Tasks

Scrambled arrivals
Enqueue (3, A), (1, B), (2, C) and predict the dequeue order.
Priority jump
Insert a priority-0 item after several others and watch it be served next.
Naive vs heap
State the cost of a scan-based dequeue versus a heap-based one.

Self-check

Dequeue order follows priority, not arrival.
The student predicts the next served element correctly.
The O(n) vs O(log n) distinction is stated.

Environment

priority-ordered viewenqueuedequeuepriority tagstie-break rules