Heaps: LeftistHeap

Node-based leftist heap with efficient merge. Unlike array-based MinHeap, merge is the fundamental primitive.

See also: SkewHeap — simpler merge-based heap with similar amortized performance.

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) - logarithmic time
  • O(k) - linear time proportional to the argument size

heap/leftist-heap.js

Implementation of LeftistHeap.

import LeftistHeap from 'list-toolkit/heap/leftist-heap.js';

const heap = new LeftistHeap();

Class LeftistHeapNode

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

Class LeftistHeap

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 leftist heaps into this heap	O(k log k)
clone()	LeftistHeap	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 LeftistHeap instances; source heaps are cleared after merge.

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

The merge recursion is bounded by the leftist rank — O(log n) stack. clone() is iterative: its explicit stack is heap-allocated, so deep left spines cannot overflow the call stack (and cloned nodes keep their ranks).

Static methods

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

Exports

LeftistHeap is the default export. LeftistHeapNode is exported by name.