Heaps: SkewHeap

Node-based skew heap with efficient merge. Simpler variant of LeftistHeap — unconditionally swaps children during merges instead of tracking rank.

Legend for tables

• API
  • options - an object with optional properties: less and compare:
    • less(a, b) - a function prototyped as a < b (the default)
    • compare(a, b) - a standard comparison function. If specified, it overrides less.
  • value - the value to be stored in the heap
• Complexity
  • O - complexity of an operation
  • O(1) - constant time
  • O(n) - linear time proportional to the heap size
  • O(log n) - amortized logarithmic time
  • O(k) - linear time proportional to the argument size

heap/skew-heap.js

Implementation of SkewHeap.

import SkewHeap from 'list-toolkit/heap/skew-heap.js';

const heap = new SkewHeap();

Class SkewHeapNode

Internal node. Properties: value, left, right. Methods: clear(), clone().

Class SkewHeap

Methods:

Member	Return type	Description	O
constructor(options = null, ...args)	this	create a new heap
root	node | null	the root node of the merge tree	O(1)
size	number	the heap's size (writable; kept in sync by mutators)	O(1)
length	number	alias getter for size	O(1)
isEmpty	truthy/falsy	checks if the heap is empty	O(1)
top	any	the heap's top element	O(1)
peek()	any	the heap's top element	O(1)
pop()	any	remove and return the heap's top element	O(log n)
push(value)	this	add an element to the heap	O(log n)
pushPop(value)	any	add an element and remove and return the top element	O(log n)
replaceTop(value)	any	return the top element and add a new element	O(log n)
clear()	this	remove all elements	O(1)
merge(...args)	this	merge other skew heaps into this heap	O(k log k)
clone()	SkewHeap	create a deep copy of the heap	O(n)

Notes on properties and methods

Optional options: less (default (a, b) => a < b), compare (standard comparator; if specified, derives less).

...args accepts other SkewHeap instances; source heaps are cleared after merge.

pushPop(value) = push then pop; replaceTop(value) = pop then push. Both more efficient than separate calls.

The skew merge is iterative — O(1) auxiliary space, and measurably faster than the recursive formulation it replaced (~1.4×: 1.88ms vs 2.67ms on the 10k push+pop cycle, 2026-07-18; the recursive variant is archived in bench/bench-heaps.js). A single merge can still take worst O(n) time with no structural bound (reached through push/pop/pushPop/replaceTop too — contrast LeftistHeap, whose rank bounds the merge path at O(log n)); amortized O(log n). clone() is iterative with a heap-allocated explicit stack — deep spines cannot overflow the call stack.

Static methods

Member	Return type	Description	O
SkewHeap.from(array, options)	SkewHeap	create a heap from an iterable	O(k log k)

Exports

SkewHeap is the default export. SkewHeapNode is exported by name.