DSAverse

Heap-like Data Structures

Loading Heap Structures...

Max Heap

root: 90

Skew Heap

A self-adjusting merge-based heap that unconditionally swaps children on every merge step — no bookkeeping needed, yet O(log n) amortized performance is guaranteed.

Heap Visualization

Watch the highlighted node swap its children (SKEW) after each recursive merge call.

Speed

Empty heap — insert values to begin

Nodes

Height

Swaps (op)

Insert values to build the heap. Notice the unconditional child swap on every merge step.

Complexity (Amortized)

O(log n)*

Insert

O(log n)*

Extract Min

O(1)

Find Min

O(log n)*

Merge

O(n)

Space

None

Per-node data

* amortized — worst case can be O(n)

The Skewing Process

1Compare roots — keep the smaller as new root (min-heap property)
2Recursively merge the larger root's subtree with the smaller root's right child
3SKEW — unconditionally swap left and right children. Always. No condition checked.

The unconditional swap distributes "heavy" nodes across the tree over time, ensuring the amortized O(log n) bound without storing any balance information.

Skew vs Leftist Heap

Extra data per nodenpl fieldnone

Swap conditionnpl(left) < npl(right)always swap

ComplexityO(log n) worstO(log n) amortized

Implementationslightly complexvery simple

Active Recall Quiz

Question 1 of 3

What makes skew heaps 'self-adjusting' and different from leftist heaps?

DSAverse

Heap-like Data Structures

Loading Heap Structures...

Max Heap

root: 90