In computer science, a shadow heap is a mergeable heap data structure which supports efficient heap merging in the amortized sense. More specifically, shadow heaps make use of the shadow merge algorithm to achieve insertion in O(f(n)) amortized time and deletion in O((log n log log n)/f(n)) amortized time, for any choice of 1 ≤ f(n) ≤ log log n.[1]
Throughout this article, it is assumed that A and B are binary heaps with |A| ≤ |B|.
Shadow merge is an algorithm for merging two binary heaps efficiently if these heaps are implemented as arrays. Specifically, the running time of shadow merge on two heaps and is .
We wish to merge the two binary min-heaps and . The algorithm is as follows:
Again, let denote the path, and denote the subtree of the concatenated heap . The number of nodes in is at most twice the depth of , which is . Moreover, the number of nodes in at depth is at most 3/4 the number of nodes at depth , so the subtree has size . Since there are at most 2 nodes at each level on , then reading the smallest elements of the shadow into the sorted array takes time.
If , then combining and as in step 5 above takes time . Otherwise, the time taken in this step is . Finally, making a heap of the subtree takes time. This amounts to a total running time for shadow merging of .
A shadow heap consists of threshold function , and an array for which the usual array-implemented binary heap property is upheld in its first entries, and for which the heap property is not necessarily upheld in the other entries. Thus, the shadow heap is essentially a binary heap adjacent to an array . To add an element to the shadow heap, place it in the array . If the array becomes too large according to the specified threshold, we first build a heap out of using Floyd's algorithm for heap construction,[2] and then merge this heap with using shadow merge. Finally, the merging of shadow heaps is simply done through sequential insertion of one heap into the other using the above insertion procedure.
We are given a shadow heap , with threshold function as above. Suppose that the threshold function is such that any change in induces no larger a change than in . We derive the desired running time bounds for the mergeable heap operations using the potential method for amortized analysis. The potential of the heap is chosen to be:
Using this potential, we can obtain the desired amortized running times:
create(H): initializes a new empty shadow heap
insert(x, H): inserts into the shadow heap
delete_min(H): deletes the minimum priority element from
A naive binary heap merging algorithm will merge the two heaps and in time by simply concatenating both heaps and making a heap out of the resulting array using Floyd's algorithm for heap construction. Alternatively, the heaps can simply be merged by sequentially inserting each element of into , taking time .
Sack and Strothotte proposed an algorithm for merging the binary heaps in time.[3] Their algorithm is known to be more efficient than the second naive solution described above roughly when . Shadow merge performs asymptotically better than their algorithm, even in the worst case.
There are several other heaps which support faster merge times. For instance, Fibonacci heaps can be merged in time. Since binary heaps require time to merge,[4] shadow merge remains efficient.