Heaps: PairingHeap

Node-based pairing heap — the practical winner of the merge-heap family: O(1) push and merge, O(log n) amortized pop, and decrease-key by node handle — push() returns the node, and update(node, true) restores the heap in O(1) amortized after the value got smaller.

See also: LeftistHeap and SkewHeap — the other merge heaps (no handle operations); IndexedHeap — array-based handles with honest O(1) membership; MinHeap — the fastest general-purpose choice when merge and handles are not needed.

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
  • node - a PairingHeapNode handle returned by push()
• 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/pairing-heap.js

Implementation of PairingHeap.

import PairingHeap from 'list-toolkit/heap/pairing-heap.js';

const heap = new PairingHeap({less: (a, b) => a.deadline < b.deadline});
const node = heap.push({deadline: 150});

// reschedule earlier: mutate, then decrease-key — O(1) amortized
node.value.deadline = 42;
heap.update(node, true);

// cancel: remove by handle — O(log n) amortized
heap.remove(node);

Class PairingHeapNode

The handle returned by push(). Properties: value (public — mutate it, then call update), child, sibling, prev (previous sibling, or the parent for a leftmost child; null for the root).

Class PairingHeap

Methods:

Member	Return type	Description	O
constructor(options = null, ...args)	this	create a new heap merging in heaps (drained) / iterables
root	node | null	the root node of the pairing tree	O(1)
size	number	the heap's size (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)
push(value)	node	add an element; returns the node handle	O(1)
pop()	any	remove and return the heap's top element	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)
update(node, isDecreased?)	this	restore the heap after mutating node.value	see notes
remove(node)	this	remove an element by handle	O(log n)
clear()	this	remove all elements (outstanding handles become invalid)	O(1)
merge(...args)	this	merge heaps (O(1) each, drained) and/or iterables (pushed)	O(k)
clone()	PairingHeap	create a deep copy (new nodes — old handles stay with original)	O(n)

Notes on properties and methods

Handles: push() returns the PairingHeapNode — keep it to update/remove that element later, the same way list methods return Ptrs. Handles are owned by the heap that returned them: passing a node from another heap, or one already popped, is undefined behavior (no membership validation — use IndexedHeap when honest O(1) has() matters).

update(node, isDecreased?): after mutating node.value, pass isDecreased = true when the value got smaller — the classic decrease-key, O(1) amortized (cut + meld, the subtree rides along). Omit it (or pass false) for the general case — O(log n) amortized (the node's children are re-paired and re-melded), correct in both directions.

merge() melds each PairingHeap argument in O(1) and drains it; iterables are pushed value by value. This is the cheapest merge in the family (leftist: O(log n); skew: O(log n) amortized).

Auxiliary space: the two-pass pairing in pop() (and the re-pairing paths of update()/remove()) is O(1) — pass 1 chains pair winners in reverse through their momentarily-free sibling pointers, so no transient array is needed regardless of the root's child count.

Benchmarked (10k push+pop cycle, 2026-07-18, bench/bench-heaps.js): PairingHeap 2.60ms, SkewHeap 1.91ms (fastest of the node-based trio since its merge went iterative), LeftistHeap 3.88ms; array-based MinHeap 0.97ms remains the general-purpose choice when merge and handles are not needed. PairingHeap keeps the O(1) meld and the handle operations the skew heap lacks.

Static methods

Member	Return type	Description	O
PairingHeap.from(values, options)	PairingHeap	create a heap from an iterable	O(k)

Exports

PairingHeap is the default export. PairingHeap and PairingHeapNode are also exported by name.