Shadow heap

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".
Throughout this article, it is assumed that "A" and "B" are binary heaps with |"A"| ≤ |"B"|.
Shadow merge.
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 formula_1 and formula_2 is formula_3.
Algorithm.
We wish to merge the two binary min-heaps formula_1 and formula_2. The algorithm is as follows:
Running time.
Again, let formula_14 denote the path, and formula_16 denote the subtree of the concatenated heap formula_8. The number of nodes in formula_14 is at most twice the depth of formula_8, which is formula_36. Moreover, the number of nodes in formula_16 at depth formula_38 is at most 3/4 the number of nodes at depth formula_39, so the subtree has size formula_40. Since there are at most 2 nodes at each level on formula_14, then reading the smallest formula_17 elements of the shadow into the sorted array formula_18 takes formula_36 time.
If formula_20, then combining formula_14 and formula_8 as in step 5 above takes time formula_48. Otherwise, the time taken in this step is formula_49. Finally, making a heap of the subtree formula_16 takes formula_40 time. This amounts to a total running time for shadow merging of formula_52.
Structure.
A shadow heap formula_53 consists of threshold function formula_54, 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 formula_2 adjacent to an array formula_1. To add an element to the shadow heap, place it in the array formula_1. If the array becomes too large according to the specified threshold, we first build a heap out of formula_1 using Floyd's algorithm for heap construction, and then merge this heap with formula_2 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.
Analysis.
We are given a shadow heap formula_60, with threshold function formula_61 as above. Suppose that the threshold function is such that any change in formula_62 induces no larger a change than in formula_54. We derive the desired running time bounds for the mergeable heap operations using the potential method for amortized analysis. The potential formula_64 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 formula_53
insert("x", "H"): inserts formula_69 into the shadow heap formula_53
delete_min("H"): deletes the minimum priority element from formula_53
Related algorithms & data structures.
A naive binary heap merging algorithm will merge the two heaps formula_1 and formula_2 in time formula_82 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 formula_1 into formula_2, taking time formula_85.
Sack and Strothotte proposed an algorithm for merging the binary heaps in formula_86 time. Their algorithm is known to be more efficient than the second naive solution described above roughly when formula_87. 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 formula_68 time. Since binary heaps require formula_89 time to merge, shadow merge remains efficient.