Skew Heap Algorithm
The Skew Heap Algorithm is a simple and efficient data structure used for implementing priority queues. It is a self-adjusting binary heap that works on the concept of merging two heaps to maintain heap order property, which states that the key of each node must be greater (or smaller) than the keys of its children. Skew heaps are particularly useful in scenarios where insertions and deletions happen frequently, as they are able to adjust their structure efficiently. The algorithm is based on the merge operation and operates in amortized logarithmic time, providing a faster alternative to other priority queue implementations such as binary heaps and Fibonacci heaps.
A skew heap is a self-adjusting form of a leftist heap, which is a variant of a binary heap. Unlike binary heaps, skew heaps do not have a fixed structure and shape, making them more flexible and adaptable. The primary difference between a skew heap and a leftist heap lies in the way they maintain the heap property. While leftist heaps maintain a balance by keeping track of the shortest distance to a leaf node and merging nodes accordingly, skew heaps take a more relaxed approach by simply swapping the left and right children of each node after a merge operation. This simple yet effective technique helps skew heaps maintain the heap property while also ensuring that the height of the tree remains minimal, thus optimizing the overall performance of the algorithm.
/**
*
* -Notes-
*
* A skew heap is a self-adjusting form of a leftist heap which attempts to
* maintain balance by unconditionally swapping all nodes in the merge path
* when merging two heaps. (The merge operation is also used when adding
* and removing values.)
*
* With no structural constraints, it may seem that a skew heap would be horribly
* inefficient. However, amortized complexity analysis can be used to demonstrate
* that all operations on a skew heap can be done in O(log n).
*
* Wikipedia: http://en.wikipedia.org/wiki/Skew_heap
* Self-Adjusting Heaps: http://www.cs.cmu.edu/~sleator/papers/Adjusting-Heaps.htm
* Union-Based Heaps: https://speakerdeck.com/kachayev/union-based-heaps?slide=22
*
*/
abstract sealed class Heap[+A <% Ordered[A]] {
/**
* Min value 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]
/**
* Whether this heap is empty or not.
*/
def isEmpty: Boolean
/**
* The 'insert' function might be defined through the 'Heap.merge' function
*
* Time - O(log n)
* Space - O(log n)
*/
def insert[B >: A <% Ordered[B]](x: B): Heap[B] =
Heap.merge(Heap.make(x), this)
/**
* Removes the minimum element from this heap.
*
* Time - O(log n)
* Space - O(log n)
*/
def remove: Heap[A] = Heap.merge(left, right)
/**
* Fails with message.
*/
def fail(m: String) = throw new NoSuchElementException(m)
}
/**
* Empty node representation
*/
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 isEmpty = true
}
/**
* Non-empty node is an element with left and right childs (Skew Heaps)
*/
case class Branch[A <% Ordered[A]](min: A, left: Heap[A], right: Heap[A]) extends Heap[A] {
def isEmpty = false
}
object Heap {
/**
* An empty heap.
*/
def empty[A]: Heap[A] = Leaf
/**
* Makes a heap node.
*/
def make[A <% Ordered[A]](x: A, l: Heap[A] = Leaf, r: Heap[A] = Leaf) =
Branch(x, l, r)
/**
* Merges two given heaps. Also known as "union".
*
* When two skew heaps are to be merged, we can use a similar process as the merge of two leftist heaps:
*
* - Compare roots of two heaps; let p be the heap with the smaller root, and q be the other heap.
* Let r be the name of the resulting new heap.
* - Let the root of r be the root of p (the smaller root), and let r's right subtree be p's left subtree.
* - Now, compute r's left subtree by recursively merging p's right subtree with q.
*
* More about "merge" operation: http://en.wikipedia.org/wiki/Skew_heap#Operations
*
* Time - O(log n)
* Space - O(log n)
*/
def merge[A <% Ordered[A]](x: Heap[A], y: Heap[A]): Heap[A] = (x, y) match {
case (_, Leaf) => x
case (Leaf, _) => y
case (Branch(x1, l1, r1), Branch(x2, l2, r2)) =>
if (x1 < x2) Branch(x1, Heap.merge(Branch(x2, l2, r2), r1), l1)
else Branch(x2, Heap.merge(Branch(x1, l1, r1), r2), l2)
}
/**
* Builds a skew heap from an unordered linked list.
*/
def fromList[A <% Ordered[A]](ls: List[A]): Heap[A] = {
def loop(hs: List[Heap[A]]): Heap[A] = hs match {
case hd :: Nil => hd
case _ => loop(pass(hs))
}
def pass(hs: List[Heap[A]]): List[Heap[A]] = hs match {
case hd :: nk :: tl => Heap.merge(hd, nk) :: pass(tl)
case _ => hs
}
if (ls.isEmpty) Heap.empty
else loop(ls.map(Heap.make(_)))
}
}
