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 