Standard Heap Algorithm
The Standard Heap Algorithm, also known as Heap's Permutation Algorithm, is a powerful and efficient method to generate all possible permutations of a given sequence. Devised by B. R. Heap in 1963, this algorithm is based on the concept of recursion, where the solution to a problem is constructed progressively by reducing it to simpler versions of the same problem. The algorithm is particularly useful in combinatorial mathematics, computer science, and other fields that require the manipulation of ordered sets, particularly when a brute-force approach of checking all possible permutations is computationally expensive or impractical.
The main idea behind Heap's algorithm is to generate permutations by swapping elements in the sequence. The algorithm starts with the initial sequence and recursively generates permutations by swapping elements at certain positions, working its way down to a sequence of size one – the base case of the recursion. The key feature of Heap's algorithm is that it minimizes the number of swaps required to generate all permutations, making it more efficient than other permutation generation methods such as the Steinhaus–Johnson–Trotter algorithm. Furthermore, Heap's algorithm can be easily implemented in various programming languages, making it a popular choice for tasks requiring permutation generation.
/**
* This file is part of Scalacaster project, https://github.com/vkostyukov/scalacaster
* and written by Vladimir Kostyukov, http://vkostyukov.ru
*
* Heap http://en.wikipedia.org/wiki/Heap_(data_structure)
* Binary Heap http://en.wikipedia.org/wiki/Binary_heap
*
* Min - O(1)
* Remove - O(log n)
* Insert - O(log n)
* Merge - O(n)
*
* -Notes-
*
* There is an article that describes all the ideas behind this implementation:
*
* http://arxiv.org/pdf/1312.4666v1.pdf
*
* This is an efficient implementation of binary heap that grantees O(log n) running
* time for insert/remove operations.
*
* There are two invariants of binary heaps:
*
* 1. Shape-property - the heap - is a complete binary tree.
* 2. Heap-property - children's elements should be less or equal to parent's.
*
* These invariants complete by two main ideas. The first thing is there are (2^n - 1)
* nodes in a complete binary tree. This can be used in insertion for choosing right
* search path. To guarantee O(log n) insertion running time two node parameters can be
* used - 'height' and 'size'. So, the condition looks like following:
*
* node.size < math.pow(2, node.height) - 1
*
* The second thing is bubbling that goes up to search path and swapping nodes to
* correspond heap property.
*
* Removal it is always pain in the neck. There are three phases of removal minimum
* element from binary heap:
*
* 1. Find latest inserted node.
* 2. Replace root value with this node's value.
* 3. Fix all heap property violations by bubbling root element down.
*
* These can be done in O(log n) time.
*
* Heap construction can be performed in O(n) time by using following approach:
*
* 1. Insert all items into the heap to satisfy 'shape invariant'.
* 2. Fix all violations of 'heap invariant' by bubbling nodes up.
*
*/
abstract sealed class Heap[+A <% Ordered[A]] {
/**
* Minimum of this heap.
*/
def min: A
/**
* The left child of this heap.
*/
def left: Heap[A]
/**
* The right child of this heap.
*/
def right: Heap[A]
/**
* The size of this heap.
*/
def size: Int
/**
* The height of this tree
*/
def height: Int
/**
* Checks whether this heap empty or not.
*/
def isEmpty: Boolean
/**
* Inserts given element 'x' into this heap.
*
* Time - O(log n)
* Space - O(log n)
*/
def insert[B >: A <% Ordered[B]](x: B): Heap[B] =
if (isEmpty) Heap.make(x)
else if (left.size < math.pow(2, left.height) - 1)
Heap.bubbleUp(min, left.insert(x), right)
else if (right.size < math.pow(2, right.height) - 1)
Heap.bubbleUp(min, left, right.insert(x))
else if (right.height < left.height)
Heap.bubbleUp(min, left, right.insert(x))
else Heap.bubbleUp(min, left.insert(x), right)
/**
* Removes minimum element from this heap.
*
* Time - O(log n)
* Space - O(log n)
*/
def remove: Heap[A] = {
def floatLeft[A <% Ordered[A]](x: A, l: Heap[A], r: Heap[A]): Heap[A] = l match {
case Branch(y, lt, rt, _, _) => Heap.make(y, Heap.make(x, lt, rt), r)
case _ => Heap.make(x, l, r)
}
def floatRight[A <% Ordered[A]](x: A, l: Heap[A], r: Heap[A]): Heap[A] = r match {
case Branch(y, lt, rt, _, _) => Heap.make(y, l, Heap.make(x, lt, rt))
case _ => Heap.make(x, l, r)
}
def mergeChildren(l: Heap[A], r: Heap[A]): Heap[A] =
if (l.isEmpty && r.isEmpty) Heap.empty
else if (l.size < math.pow(2, l.height) - 1)
floatLeft(l.min, mergeChildren(l.left, l.right), r)
else if (r.size < math.pow(2, r.height) - 1)
floatRight(r.min, l, mergeChildren(r.left, r.right))
else if (r.height < l.height)
floatLeft(l.min, mergeChildren(l.left, l.right), r)
else floatRight(r.min, l, mergeChildren(r.left, r.right))
def bubbleRootDown(h: Heap[A]): Heap[A] =
if (h.isEmpty) Heap.empty
else Heap.bubbleDown(h.min, h.left, h.right)
if (isEmpty) fail("An empty heap.")
else bubbleRootDown(mergeChildren(left, right))
}
/**
* Fails with given message.
*/
def fail(m: String) = throw new NoSuchElementException(m)
}
case class Branch[A <% Ordered[A]](min: A, left: Heap[A], right: Heap[A], size: Int, height: Int) extends Heap[A] {
def isEmpty: Boolean = false
}
case object Leaf extends Heap[Nothing] {
def min: Nothing = fail("An empty heap.")
def left: Heap[Nothing] = fail("An empty heap.")
def right: Heap[Nothing] = fail("An empty heap.")
def size: Int = 0
def height: Int = 0
def isEmpty: Boolean = true
}
object Heap {
/**
* Returns an empty heap.
*/
def empty[A]: Heap[A] = Leaf
/**
* A smart constructor for heap's branch.
*/
def make[A <% Ordered[A]](x: A, l: Heap[A] = Leaf, r: Heap[A] = Leaf): Heap[A] =
Branch(x, l, r, l.size + r.size + 1, math.max(l.height, r.height) + 1)
/**
* Creates a new heap from given sorted array 'a'.
*
* Time - O(n)
* Space - O(log n)
*/
def fromSortedArray[A <% Ordered[A]](a: Array[A]): Heap[A] = {
def loop(i: Int): Heap[A] =
if (i < a.length) Heap.make(a(i), loop(2 * i + 1), loop(2 * i + 2))
else Heap.empty
loop(0)
}
/**
* Creates a new heap from given array 'a'.
*
* Time - O(n)
* Space - O(log n)
*/
def fromArray[A <% Ordered[A]](a: Array[A]): Heap[A] = {
def loop(i: Int): Heap[A] =
if (i < a.length) Heap.bubbleDown(a(i), loop(2 * i + 1), loop(2 * i + 2))
else Heap.empty
loop(0)
}
/**
* Bubbles given heap ('x', 'l', 'r') up.
*
* Time - O(1)
* Space - O(1)
*/
private[Heap] def bubbleUp[A <% Ordered[A]](x: A, l: Heap[A], r: Heap[A]): Heap[A] = (l, r) match {
case (Branch(y, lt, rt, _, _), _) if (x > y) =>
Heap.make(y, Heap.make(x, lt, rt), r)
case (_, Branch(z, lt, rt, _, _)) if (x > z) =>
Heap.make(z, l, Heap.make(x, lt, rt))
case (_, _) => Heap.make(x, l, r)
}
/**
* Bubbles given heap ('x', 'l', 'r') down.
*
* Time - O(log n)
* Space - O(log n)
*/
private[Heap] def bubbleDown[A <% Ordered[A]](x: A, l: Heap[A], r: Heap[A]): Heap[A] = (l, r) match {
case (Branch(y, _, _, _, _), Branch(z, lt, rt, _, _)) if (z < y && x > z) =>
Heap.make(z, l, Heap.bubbleDown(x, lt, rt))
case (Branch(y, lt, rt, _, _), _) if (x > y) =>
Heap.make(y, Heap.bubbleDown(x, lt, rt), r)
case (_, _) => Heap.make(x, l, r)
}
}
