Heap / Priority Queue

heap[]

5

3

8

1

9

2

7

Default

Active

Comparing

Swapping

In Place

Removed

Time

O(N)

Space

O(N)

Debugger · v1.0

LIVE

1function buildHeap(arr) {

2 heap = [...arr];

3 const start = Math.floor(n / 2) - 1;

4 for (let i = start; i >= 0; i--) {

5 siftDown(i);

6 }

7}

Debugger · v1.0

LIVE

1function buildHeap(arr) {

2 heap = [...arr];

3 const start = Math.floor(n / 2) - 1;

4 for (let i = start; i >= 0; i--) {

5 siftDown(i);

6 }

7}

State Inspector

?

No variables in scope.

Array:

1x

Heap / Priority Queue Visualizer

Build Heap — Floyd's Algorithm

Step 1 of 6

Given an unsorted array, Floyd's algorithm builds a valid heap in O(N) time — significantly better than inserting each element one-by-one which costs O(N log N).

Why O(N) and Not O(N log N)?

Floyd's insight: leaves don't need sifting. Starting from the last non-leaf and going up to root, each sift-down is bounded by the node's height, not the full tree height. The sum of all heights = O(N).

N × InsertO(N log N)each insert bubbles up full height

Floyd's siftDownO(N)most nodes are near leaves (short sifts)