Heaps: LeftistHeap

A leftist heap is a merge-based heap data structure. See the Wikipedia's Leftist tree article for more details.

Unlike MinHeap, which is array-based, LeftistHeap is a node-based tree where the merge operation is the fundamental primitive. This makes merging two heaps very efficient.

See also: SkewHeap — a 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

This is the implementation of the LeftistHeap class.

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

const heap = new LeftistHeap();

Class LeftistHeapNode

LeftistHeapNode is used internally to represent nodes in the leftist heap. It defines the following properties:

• value — the value of the node
• left — the left child
• right — the right child
• s — the s-value (rank) used to maintain the leftist property

And the following methods:

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

Class LeftistHeap

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 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

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 LeftistHeap 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
LeftistHeap.from(array, options)	LeftistHeap	create a heap from an iterable	O(k log k)

Exports

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