Heap with $O(1)$ delete-key

Fibonacci heaps have $O(1)$ insertion and $O(\log n)$ delete-min and delete-key (under amortized complexity). Is there a heap data structure with $O(1)$ insertion and delete-key and $O(\log n)$ delete-min and find-min? That is, can delete-key be reduced to $O(1)$ at the cost of more expensive other operations such as find-min, meld, and reduce-key? Here delete-key means remove a particular key given a pointer to that key in the data structure.

This data structure would be necessary to fix my broken answer to this question: Nontrivial algorithm for computing a sliding window median.

• If so, then find-min would have to be $\Omega(\lg n)$, since otherwise delete-min, which is just the composition of find-min and delete, would be $o(\lg n)$, breaking the sorting bound via heapsort. Mar 28 '14 at 2:00
• Yes, $\Theta(\log n)$ find-min is fine for my purposes. I'll update the question to clarify. Mar 28 '14 at 15:20
• it is possible to delete the min key at the time of building min heap ?
– user29196
Dec 2 '14 at 9:21

To the best of my knowledge, no heap data structure matches your requirements. In terms of complexity, the best one is the Brodal queue, a heap data structure with worst case $O(1)$ time for insertion, find-minimum, meld (merge two queues) and decrease-key, and $O(\log~n)$ for delete-minimum and general deletion. However, this data structure is only of theoretical interest.
If you depart from the comparison-based model and adopt the RAM model where keys are regarded as binary strings, each one contained in one or more machine words, the best you can achieve for both insert and delete operations $\mathcal{O}(\sqrt{\log \log n})$. See my answer to this question.
• I don't see how $O(1)$ delete-key is problematic for the priority queue to sorting reduction. Usually heap sort does all the insertions before the delete-mins. If we know that delete-mins occur after deletion-keys, for example, it's trivial to make delete-key $O(1)$: just add newly inserted elements to a linked list and actually insert them only when the first delete-min is called. Deleting from the linked list can then happen in $O(1)$ time. Mar 29 '14 at 18:49