Heaps: SkewHeap

A skew heap is a merge-based heap data structure. See the Wikipedia's Skew heap article for more details.

Unlike MinHeap, which is array-based, SkewHeap is a node-based tree where the merge operation is the fundamental primitive. A skew heap is a simpler variant of a LeftistHeap that unconditionally swaps children during merges instead of maintaining rank information.

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

This is the implementation of the SkewHeap class.

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

const heap = new SkewHeap();

Class SkewHeapNode

SkewHeapNode is used internally to represent nodes in the skew heap. It defines the following properties:

• value — the value of the node
• left — the left child
• right — the right child

And the following methods:

• clear() — reset children to null
• clone() — recursively clone the subtree

Class SkewHeap

This class provides the following 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

An options object can be passed to the constructor. Its less and compare properties are optional. The defaults are:

• less = (a, b) => a < b
• compare = null

If compare is specified, it is used to derive less, overwriting its value.

Methods that take ...args use them to merge into the heap. args should be other SkewHeap instances. The source heaps are cleared after the merge.

pushPop(value) is a combination of push(value) and pop(). replaceTop(value) is a combination of pop() and push(value). They are provided because they can be implemented more efficiently than calling push() and pop() separately.

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 exported as SkewHeap and as the default export. SkewHeapNode is exported by name.