) x1 = 1, and so case 1 would apply, a contradiction. Thus x0 > 1. Then let y0 = 1, yi = xi - 1 for i > 0. Using similar logic to the above (and the fact that L(0) = L(1) = 1), the sum of these y's is equal to n + 1. Since x0 > 1, the y's are in ascending order. x0 ≠ 0, so the third claim does not apply. Finally, since case one did not apply, x0 + 1 < x1, and so the final claim holds, and the claim holds for n + 1
These three cases are exhaustive and mututally exclusive, and so the induction is complete.
Finally, we need to show that each of the sequences described above uses at most O(lg n) Leonardo numbers. To do this, we show that L(k) = 2 F(k + 1) - 1, where F(k + 1) is the (k+1)st Fibonacci number. From there, we have that L(k) > (2 / √5)φ(k + 1), with φ = (1 + √ 5) / 2 by the closed-form equation for Fibonacci numbers.. We then have that for any n, if we let k = ⌈ logφ((√5/2) n) ⌉ = O(lg n), we have that L(k) > n. Since n can be written as the sum of unique Leonardo numbers, none of which can be bigger than n (and thus no greater than L(k)), this means that n can be written as the sum of some subset of the first k Leonardo numbers, of which there are only O(lg n).
The proof that L(k) = 2F(k + 1) - 1 is by induction on k. For k = 0, 2F(1) - 1 = 2 - 1 = 1 = L(0). For k = 1, 2F(2) - 1 = 2 - 1 = 1 = L(1). Now assume that for all k' < k, the claim holds. Then L(k) = L(k - 2) + L(k - 1) + 1 = 2F(k - 1) - 1 + 2F(k) - 1 + 1 = 2(F(k - 1) + F(k)) - 1 = 2F(k + 1) - 1.
QED
Much in the same way that you can build a binomial heap using a collection of binomial trees (not required reading, but highly recommended!), you can build a "Leonardo heap" out of a collection of Leonardo trees. A Leonardo heap is an ordered collection of Leonardo trees such that:
Here is a sample Leonardo heap:
Notice that properties (1) and (3) of Leonardo heaps mean that the smallest heap has the largest root and the largest heap has the smallest root. The roots increase from left to right.
In order for Leonardo heaps to qualify as max-heaps, we'll need to implement some basic functionality on them. In particular, we'll show how to implement heap insert and dequeue-max.
Inserting into a Leonardo heap. There are three steps to inserting into a Leonardo heap. First, we need to ensure that the resulting heap has the correct shape; that it's a collection of Leonardo trees of unique size stored in descending order of size. Next, we need to ensure that the tops of the heaps are sorted in ascending order from left to right. Finally, we'll ensure that each of the Leonardo trees obeys the max-heap property. Let's start by seeing how to get the shape right.
Earlier we proved that each number can be partioned into a sum of descending, unique Leonardo numbers obeying certain properties, and the algorithm for inserting into a Leonardo heap is based on the three cases of the proof. We begin by checking whether the two smallest Leonardo trees correspond to consecutive Leonardo numbers L(k) and L(k + 1). If so, we create a new Leonardo tree of type Lt(k+2) with the inserted element as the root. Otherwise, if the smallest Leonardo tree is of size L(1), we insert the new element as a singleton Leonardo tree of size L(0). Finally, if neither other case applies, we insert the new element as a singleton Leonardo tree of size L(1). The proof that this ends up producing a sequence of Leonardo trees of decreasing size is almost identical to the earlier proof, and so I omit it. Here are a few pictures of different insertions into a Leonardo heap:
Now, let's see how to guarantee that the topmost elements of each heap are sorted in ascending order from left to right. Essentially, this step does an insertion sort of the new value into the list defined by the roots of all of the Leonardo trees, though it's a bit more complex than that. In particular, because the new element is not necessarily the largest element of the tree containing it (because we haven't yet restored the heap property), if we naively swap the new element down until it comes to rest, we can't be guaranteed that the heap property will hold for any of the heaps that were modified. For example, consider this setup, which corresponds to the state of the Leonardo heap in the third of the above examples:
Here, the root of the rightmost heap (the number 54) was just added. If we naively insertion sort it down to its proper resting place, then in the end we might need to restore the heap property for each of the heaps we swapped roots with, as seen by the fact that the new root of the rightmost heap is smaller than any of its elements.
The problem with this is that what we really want to do is insertion sort on the values that will ultimately be at the roots of the trees. Furthermore, we'd like to do this as efficiently as possible; that is, without reheapifying each tree at every step. Fortunately, we can do this fairly easily. Given a "mostly-heapified" Leonardo tree (one where the root may be out of place, but the rest of the structure is valid), we can guarantee that the node that ultimately ends up being the root of the tree is either the root or the roots of one of its two children. Consequently, we do a modified insertion sort, swapping the root of the preceding tree with the current one only if its root is bigger than the new element and the roots of its child nodes. Note that if this is true, after the swap the tree that used to contain the new element is now a correctly-balanced heap, since the new root is bigger than either of the roots of the subtrees.
Finally, once we end up in a situation where the new root is atop the correct heap, we can use the heapify operation originally developed for binary heaps to restore the heap property to that tree. At this point, as mentioned above, all of the trees to the right are valid max-heap Leonardo trees, the current tree is valid, and the trees to the left are all unchanged. Moreover, the roots of the trees are in descending order, since we used an (albeit modified) insertion sort to rearrange them.
Let's consider the runtime of this operation. Creating a new Leonardo tree from the new element and (possibly) the two preceding trees can be done in O(1). The insertion sort step might move the new element across the tops of at most O(lg n) trees (since, as mentioned before, the partitioning of the n elements into distinct Leonardo numbers uses at most O(lg n) such numbers), and when it finally comes to rest, it's inserted into a Leonardo tree of order at most O(lg n). A quick inductive argument can be shown that the height of a Leonardo tree of size k is O(k), and so this bubble-down step takes at most O(lg n) time, netting an insert time of O(lg n).
However, what if the element we're inserting is the largest element in the heap? In that case, the heap-building runtime is the same, but the time to insertion-sort the element into place is now O(1) instead of O(lg n), and the time to heapify the tree containing the new element is also O(1) since no rearrangements are made. In other words, inserting a new max element into a Leonardo heap takes time O(1). This is crucial to getting smoothsort to run in O(n) time on already-sorted inputs.
Dequeuing elements from a Leonardo heap.. This process is similar to the process for building a Leonardo heap, though with a bit more bookkeeping. We know that the largest element is atop the smallest heap, and so we can dequeue it quite easily. There are now two cases to consider, depending on what kind of heap the last element was in. If it was a Lt0 or Lt1 heap, then all of the guarantees we had about the heap structure still hold, since all we did was remove a heap from the front of the list. Otherwise, the heap has two child heaps which have just been "exposed" to the rest of the trees. To rebalance the heap, we apply the modified insertion sort algorithm to reposition the root of the leftmost tree, then heapify whichever tree the root ends up in. We then do the same for the rightmost tree. Once this step is complete, all of the heap properties are satisfied and we are done.
Here are some examples of Leon