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
length	number	the heap's 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.

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.