Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Concept

Overview

Complete tree + heap property · sift-up / sift-down
step 1 / 17
max-heap
♦500
301
402
103
204
355
array form · child(i) = 2i+1, 2i+2
50
30
40
10
20
35
[0][1][2][3][4][5]
Concept
▸
1// complete binary tree, stored as an array
2parent(i) = ⌊(i−1)/2⌋
3left(i) = 2i+1   right(i) = 2i+2
4peek():   return arr[0]            // O(1)
5 
6push(x):
7    append x; sift it UP
8        while x > parent: swap up
9 
10pop():
11    save arr[0]; move last leaf to root
12    sift it DOWN
13        while < larger child: swap down
14    return saved
state
  • typemax-heap
  • root50

line 1A binary heap is a COMPLETE binary tree (filled left-to-right, no gaps) obeying one rule — the HEAP PROPERTY. In a MAX-heap every parent is ≥ both its children, so the maximum is always at the root.