Heap Simulator

See min-heap and max-heap insertion, extraction and heapify as both a tree and an array, one swap at a time.

Operations

ValueBuild heap from list (up to 15)

Every parent now beats its children: it's a heap. Building this way takes O(n) time.

Min-heap

Every parent is ≤ its children, so the smallest value is always at the root.

Drag to move · scroll to zoom

Stored as an array

101

252

153

404

305

356

507

For index i: parent = (i − 1) DIV 2, left child = 2i + 1, right child = 2i + 2. No pointers are needed.

Pseudocode

The current line is highlighted.

About This Simulation

This heap simulator shows min-heaps and max-heaps as both a tree and the array that stores it. Insertion sifts the new value up, extraction moves the last value to the root and sifts it down, and build-heap turns any list into a heap from the bottom up, one swap at a time.

Features

Min-heap and max-heap modes
Insert with sift-up shown swap by swap
Extract the root with sift-down
Build a heap from your own list (bottom-up heapify)
Tree view and array view kept in sync, with indices
Pseudocode with the active line highlighted

Topics covered

Binary Heap
Min-Heap and Max-Heap
Heapify
Sift Up and Sift Down
Priority Queue
Heap Sort

Explanation

A binary heap is a complete binary tree with the heap property: in a min-heap every parent is less than or equal to its children, and in a max-heap every parent is greater than or equal to its children. The best value is therefore always at the root. Because the tree is complete, it is stored in an array with no pointers.

How it works

In the array, the children of index i are at 2i + 1 and 2i + 2, and its parent is at (i − 1) DIV 2.
Insert: add the value at the end of the array, then sift it up, swapping with its parent while it beats the parent.
Extract: remove the root, move the last value to the root, then sift it down, swapping with its better child while that child beats it.
Build a heap: starting from the last node that has children and working back to the root, sift each node down. This takes O(n) time.
Insert and extract each take O(log n) time because the tree's height is log₂ n.

Why it matters

Heaps implement priority queues, which are used in Dijkstra's and Prim's algorithms, CPU scheduling, event simulation and Huffman coding. Heap sort also uses a heap. They are a core topic in CSE220 and CSE221.

Frequently Asked Questions

What is the difference between a heap and a binary search tree?

A BST orders left and right subtrees (smaller left, larger right) for searching. A heap only orders parents against children, which keeps the minimum or maximum at the root but does not support fast searching.

Why is a heap stored in an array?

A heap is a complete tree, so there are no gaps. Each node's parent and children can be found with simple index arithmetic, saving the memory used by pointers.

What is the time complexity of heap operations?

Peek at the root: O(1). Insert and extract: O(log n). Building a heap from n items: O(n).

Related Simulations

Data Structures