Your requirements are very specific - you are only interested in these two operations: insert O (log n) and deleteMin O (1).
None of the known heap structures satisfies your specific constraints. Instead, the best structure (albeit theoretically Galactic structures , as some have called it) is Brodal Queue , which performs all heap operations in O (1) in the worst case, except deleteMin, which still takes O (lg n) worst time. All other famous structures are no better.
Since you are only interested in these two operations, you can leave with a custom structure that handles these two operations well, since you do not need to worry about key reduction, merging, etc. that more general heap structures should be worried.
Maintaining a dual DL structure containing:
- A dynamic array is sorted, D, for which you can perform a search in O (log n) using a binary search.
- A sorted linked list, L, from which you can make deleteMin in O (1), and insert the job followed by (or predecessor) into O (1) the worst time.
- A sorted list of T items recently inserted in L but not yet synchronized with D.
In addition, keep in touch between each entry in L and its corresponding entry in D or T and vice versa. In addition, you will need to maintain a bit for each D entry indicating whether it was deleted in L or not. To later conduct a mass synchronization between D and L, you can also track the number of deletions d, from L since the last synchronization. You can synchronize after the following invariant:
- Invariant 1: d + | T | <n
broken. Thus, the synchronization time remains linear in n, and you can always guarantee | T | and d are within acceptable limits.
So, to insert a new element e into DL, first do a search (e) in D for its successor (predecessor) and another search for its successor in T and take the link of the larger successor (smaller predecessor) and use this to insert in L and add e in T and maintain links. After inserting e, we check if invariant 1 is not violated. If so, we start synchronization.
Synchronization essentially combines the contents of T and D, deleting elements marked as deleted in the new structure D. This can be done in time linear in | T | + | D | = O (n). In another linear time, the links between L and D can be updated. The cost of this mass synchronization can be allocated (amortized) over insertions and deletions. For this reason, these costs are only amortized costs.
To do deleteMin, you simply delete the L head and use its backlink to D to mark its corresponding entry in D as deleted and increase d.
Observation 1 . Note: deleteMin always deletes the minimum element, since L is always updated.
Observation 2 : D is not always synchronized with L. Perhaps it has some deleted elements (marked so), and some inserted elements are found only in T.
From observations 2, we need to plan the synchronization of D with L at some point in order to support the costs of finding and inserting O (log n). This is done when Invariant 1 is broken.
One unpleasant problem that I kind of masked is the following: how do you insert into T in logarithmic time, while retaining the ability to perform linear scanning during synchronization. Only such a balanced tree can achieve this. I played around with the idea of limiting the size of T to a logarithmic size, but that would increase the amortized cost of synchronization when enough inserts were made to start synchronization. It looks like some kind of balanced wood with carvings or even a list of passes should help here.
Feel free to criticize and suggest improvements, as I have not proven or complied with all the statements here.
Update . As pointed out by @delnan, these costs are amortized. I updated the description to emphasize this fact and redesigned for clarity. Perhaps with some deception, the depreciation can be removed, but in this case we get a different structure of the Galaxy.