CSE310 Project 2: Priority Queues

Build a command-driven min-heap priority queue in C++

Project Objective

Build a command-driven min-heap priority queue in C++ with modular design and dynamic memory management.

Key Components

  • Modular design: separate files for modularity
  • Dynamic memory management: Efficient heap operations
  • Min-heap implementation: Priority queue data structure
  • File I/O: Command processing from input files
  • Exact output formatting: Precise result formatting

Commands

Read: Load data from file
BuildHeap: Create heap from array
Insert: Add new element with priority
ExtractMin: Remove minimum priority element
DecreaseKey: Reduce element's priority
PrintArray: Show all element details
PrintHeap: Display heap structure

Complete Binary Trees

Foundation for efficient heap implementation

Definition

A complete binary tree is a binary tree where:

  • All levels are filled except possibly the last
  • The last level is filled from left to right
  • No "gaps" in the structure

Key Properties

  • Height: floor(log₂(n)) where n = number of nodes
  • Nodes at level i: at most 2ᵢ
  • Total nodes: 2ʰ to 2ʰ⁺¹-1 for height h
  • Array storage: No wasted space needed

Complete Binary Tree Example

Array Representation

Advantages for Heaps

  • No pointers needed - use array indexing
  • Cache-friendly sequential memory access
  • Simple parent-child relationships via arithmetic

What is a Heap?

A complete binary tree with the heap property

Heap Definition

A heap is a complete binary tree that satisfies the heap property.

Heap Property

A relationship between parent and child nodes that creates a consistent ordering throughout the tree.

Why Complete Binary Trees?

  • Ensures efficient array storage
  • Predictable structure for algorithms
  • Optimal height characteristics

Heap Structure

Array Representation

Array Index Formulas (1-based indexing)

Parent: floor(i/2)
Left Child: 2*i
Right Child: 2*i + 1

Note: For 0-based indexing, use parent = floor((i-1)/2), left = 2*i+1, right = 2*i+2

Max-Heap vs Min-Heap

Two types of heaps with different ordering properties

Max-Heap

Property: Parent ≥ All Children

Use Case: When you need the maximum element quickly

Root: Contains the largest element

Min-Heap

Property: Parent ≤ All Children

Use Case: When you need the minimum element quickly (Project 2)

Root: Contains the smallest element

Key Differences

Aspect
Max-Heap
Min-Heap
Root Element
Maximum
Minimum
Parent vs Children
Parent ≥ Children
Parent ≤ Children
Common Use
Priority scheduling
Shortest path algorithms

Heap Insertion Operation

Step-by-step bubble-up process

Step: 0 / 5

Algorithm Steps

1. Add element at next available position (end of array)
2. Compare with parent node
3. If violates heap property, swap with parent
4. Repeat until heap property satisfied or reach root
Click "Next Step" to begin inserting elements: 10, 20, 15, 30, 40
Time Complexity: O(log n) - at most height of tree
Total for n insertions: O(n log n)

Try Your Own Values

Heap Deletion Operation

Remove the root element and maintain heap property

Step: 0 / 5

Heap Array

Extracted Elements

Algorithm Steps

1. Save root element (min/max)
2. Replace root with last element
3. Remove last element (decrease size)
4. Restore heap property by bubbling down
Click "Next Step" to begin deletion process
Time Complexity: O(log n) - at most height of tree

Heapsort Algorithm

In-place sorting using heap operations

Phase: Build Heap

Two-Phase Algorithm

Phase 1: Build Max-Heap
Convert unsorted array into max-heap structure
Complexity: O(n) using bottom-up heapify
Phase 2: Extract Maximum Repeatedly
Swap root with last element, reduce heap size, heapify
Complexity: O(n log n)
Click "Next Step" to begin heapsort process
Total Complexity: O(n log n)
Space Complexity: O(1) - in-place sorting
Advantages: Guaranteed performance, no recursion stack

Heapify vs Insertion - Complexity Analysis

Mathematical proof of why build-heap is O(n)

Method: Build-Heap (Bottom-up)

Mathematical Analysis

Build-Heap Complexity Proof

Intuition: Most nodes are near leaves and require little work
Key insight: Nodes at height h: ≤ ⌈n/2^(h+1)⌉
Work at height h: O(h)
Total work: Σ(h=0 to log n) of (n/2^(h+1)) × h
Simplifies to: O(n × Σ(h/2^h))
Since Σ(h/2^h) = 2: Total = O(n)
Click "Next Step" to see complexity comparison

Method Comparison

Repeated Insertion Method

Complexity: O(n log n)

Insert n elements, each taking O(log n) time

n × O(log n) = O(n log n)

Bottom-up Heapify Method

Complexity: O(n)

Work decreases exponentially with height

Σ(n/2^h × h) = O(n)
Advantage: Bottom-up heapify is asymptotically faster for building heaps!

Concept Recap: Why a Heap = a Priority Queue

Min-heap priority queue with task scheduling example

Priority Queue Definition

A priority queue is an abstract data type that stores elements with priorities (numeric keys).

Core Operations

  • You can insert new elements with a given priority
  • You can extract the element with the highest or lowest priority efficiently

Project Context

You're building a min-heap priority queue → smallest key = highest priority.

Each heap node contains: ELEMENT { index, key, pos } where key represents the priority.

Heap Operations Efficiency

Heaps make priority queues efficient:

Operation
What it does
Time
BuildHeap()
Turn unordered array into heap
O(n)
ExtractMin()
Remove element with smallest key
O(log n)
Insert()
Add new element
O(log n)
DecreaseKey()
Update node's key, fixing heap order
O(log n)

Visual Example: A Min-Heap Priority Queue

Scenario: Scheduling tasks with different urgency levels (smaller number = higher priority)

Task A: Priority 5
Task B: Priority 2
Task C: Priority 8
Task D: Priority 1
Task E: Priority 4
Step: 0 / 7

Tree Structure

Array Representation (1-based indexing)

H = []
Click "Next Step" to begin the task scheduling example with step-by-step insertions