Heap Sort Visualizer

Setup Array

Sort Controls

Array Visualization

Algorithm Steps

How to Use

Setup: Enter numbers separated by commas or click "Random" to generate an array
Sort: Click "Start Sort" to begin the heap sort process
Step Through: Click "Next Step" to see each step of the algorithm execution
Run Through: Click "Run Through" to automatically execute all steps in sequence
Observe: Watch the heap building and extraction process
Reset: Click "Reset" to start over with a new sort

Colors: Orange = Root, Blue = Parent, Purple = Child, Yellow = Comparing, Light Blue = Heap Boundary, Green = Sorted

Heap Sort Concept

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements efficiently.

How it works:

Build a max heap from the unsorted array
Extract the maximum element (root) and place at end
Reduce heap size and restore heap property
Repeat until all elements are sorted
Uses heapify to maintain heap structure

Time Complexity: O(n log n) guaranteed, in-place sorting

Use Cases

Priority Queues: Foundation for implementing efficient priority queue data structures
Guaranteed O(n log n): Worst-case O(n log n) performance needed for time-critical applications
In-Place Sorting: Minimal extra space requirement ideal for memory-constrained systems
Large Datasets: Efficient for sorting millions of records without additional memory overhead
Operating Systems: Used in kernel scheduling algorithms and task prioritization
Median Finding: Finding k smallest/largest elements efficiently using heaps
Competitive Programming: Common in algorithm contests requiring guaranteed performance
External Sorting: Effective for sorting data larger than available RAM

Real-World Example

Scenario: An operating system scheduler uses heap sort to prioritize 1,000 tasks from various processes and assign CPU time efficiently based on priority levels.

Input: Task priority values [8, 3, 12, 5, 15, 2, 9, 11, 7, 4, 14, 6, 13, 1, 10...]
Process: Build max heap from all tasks, repeatedly extract highest priority task and restore heap property
Output: Tasks sorted by priority [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1...] ready for execution queue

Heap sort is ideal for OS task scheduling because it guarantees O(n log n) performance regardless of task distribution, uses minimal extra memory (1,000 tasks = only O(1) additional space), and can handle real-time constraints where worst-case performance is crucial. Unlike quick sort's O(n²) worst case, heap sort ensures predictable timing. The heap structure naturally supports priority-based operations and enables efficient task prioritization and preemption.

Benefits: Guaranteed O(n log n) time, in-place sorting, supports priority operations, predictable performance for real-time systems