Splay Heaps
January 22, 2013
We have implemented heaps (priority queues) using several different methods: leftist heaps, pairing heaps, maxiphobic heaps, binomial heaps. Today, we implement heaps using splay trees, based on an implementation in Chris Okasaki’s book Purely Functional Data Structures, which is a favorite of Programming Praxis.
Splay trees are perhaps the most famous and successful of all amortized data structures. Splay trees are a close relative of balanced binary search trees, but they maintain no explicit balance information. Instead, every operation blindly restructures the tree using some simple transformations that tend to increase balance. Although any individual operation can take as much as O(n) time, … every operation runs in O(log n) amortized time.
Okasaki explains that splay trees are inconvenient to implement in functional languages because the tree is restructured even during queries, which makes splay trees awkward to use because both the tree and the value must be returned during lookup. However, a heap only queries its minimum item, a limitation that makes it easy to implement heaps using splay trees in a functional setting.
To insert an item in a splay heap, partition the existing heap into two subtrees, one containing all elements less than or equal to the new element and one containing all elements greater than the new element, then construct a new splay tree with the new element at its root. Partitioning performs a right rotation every time it follows two left branches in a row, which reduces the depth of every node in the search path by half, thus maintaining the approximate balance of the tree.
The smallest node in a splay tree is the leftmost node in the tree, which is easy to find by following left paths, performing no restructurings along the way. Deleting the smallest node is done by traversing the path to the leftmost node, performing restructurings along the way in the same manner as partitioning.
Your task is to implement priority queues using splay heaps; you should provide insert, findMin and deleteMin operators. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] Pages: 1 2 […]
Here’s my version in Racket: Sorting via splay heap
It’s not *that* different (I’m not sure how different two Scheme implementations could really be), but there is some. For example, I went with structs rather than wrapping a vector, which at once abstracts over the backend but unfortunately makes the function names a bit longer.
One thing I’m curious about is when you would want to use something like this. It was interesting to build it, but I feel like there would be better options, either for a priority queue (just use a list, insert in linked lists is relatively fast; although the runtime would be O(n) rather than amortized O(log n)) or for sorting (quicksort has a much simpler implementation, at least IMO). I guess if someone else writes the implementation and you just use it, then most of the issues would go away. Hmm.
@jpverkamp: We have used priority queues (heaps) in several exercises: Melissa O’Neill’s method of generating primes, apportioning votes in the U S House of Representatives, Prim’s algorithm for the minimum spanning tree, calculating the streaming median, building treaps, and in puzzle exercises from Wirth, Ullman and Amazon. You can find those by clicking on the Exercises | Search item on the menu bar. Priority queues are not just for sorting!
Perhaps I phrased that incorrectly. I definitely do see the use for priority queues in all sorts of cases. Personally, I remember using them for job scheduling in an industrial situation. I was more getting at this particular implementation (using a tree as the underlying structure rather than an array with power of two offsets).
Out of curiosity, I looked up what Java’s PriorityQueue and it’s apparently implemented using a heap. So I’ve used it several times without actually realizing it. :) That being said, their implementation uses a mutable array rather than a tree to implement the heap. So slightly different.
I went ahead and implemented a mutable version using arrays (as a tree though really) and sifting rather than rotations: Splay heaps redux–imperative model.
It’s based on the OpenJDK implementation of a PriorityQueue. It seems a bit more natural to me, although I wonder if modeling the tree explicitly rather than as an array (yet still performing the swaps) would have helped even more. It ended up taking me about as long to implement this one as the other, mostly because of a pair of really sneaky off-by-one errors that only cropped up in about 5% of randomized tests…
In Clojure. It is noticeably faster than a leftist heap. On my computer, to generate the first 1,000,000 primes using the leftist heap (O’Neil algorithm) takes 7.25 seconds. Replacing the heap used with a splay heap takes 6.4 seconds.
(ns splay-heap) (defrecord Heap [left value right]) (defn first "Return the first value in a priority queue (heap) If the queue is empty, return nil." [T] (:value (loop [t T] (if (nil? (:left t)) t (recur (:left t)))))) (defn partition "Partition a splay queue" [ord t pivot] (if (nil? t) [nil, nil] ;else (let [{l :left, x :value, r :right} t] (if (ord x pivot) (if (nil? r) [t nil] ;else (let [{r1 :left, y :value, r2 :right} r] (if (ord y pivot) (let [[small, big] (partition ord r2 pivot)] [(Heap. (Heap. l x r1) y small), big]) ;else (let [[small, big] (partition ord r1 pivot)] [(Heap. l x small), (Heap. big y r2)])))) ;else (if (nil? l) [nil t] ;else (let [{l1 :left, y :value, l2 :right} l] (if (ord y pivot) (let [[small, big] (partition ord l2 pivot)] [(Heap. l1 y small), (Heap. big x r)]) ;else (let [[small, big] (partition ord l1 pivot)] [small, (Heap. big y (Heap. l2 x r))])))))))) (defn insert "Insert an item in a priority queue, the ordering predicate is used to determine the proper order for items in the queue." [ord t val] (let [[l r] (partition ord t val)] (Heap. l val r))) (defn remove "Return a new priority queue with the highest priority (based on ordering predicate) removed. Returns nil when the last element is removed." [t] (if (nil? t) nil ;else (let [{l :left, x :value, r :right} t] (if (nil? l) r ;else (let [{l1 :left, y :value, l2 :right} l] (if (nil? l1) (Heap. l2 x r) ;else (Heap. (remove l1) y (Heap. l2 x r))))))))The test is simply to use some reductions to convert to/from a list.
(load "splay-heap") (defn to-heap [s] (reduce (partial splay-heap/insert <) nil s)) (defn from-heap [H] (loop [v [], h H] (if (nil? h) v (recur (conj v (splay-heap/first h)) (splay-heap/remove h))))) (def l [522,72,45,6,532,372,952,16,560,550,535,358,271,255,240,17,194,272,251,263,31,545,5,342,540]) (-> l to-heap from-heap println) (comment output is [5 6 16 17 31 45 72 194 240 251 255 263 271 272 342 358 372 522 532 535 540 545 550 560 952] )