5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – jbapple
    Mar 28 '14 at 2:00
  • $\begingroup$ Yes, $\Theta(\log n)$ find-min is fine for my purposes. I'll update the question to clarify. $\endgroup$ Mar 28 '14 at 15:20
  • $\begingroup$ it is possible to delete the min key at the time of building min heap ? $\endgroup$
    – user29196
    Dec 2 '14 at 9:21
2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Fibonacci heaps have the same time complexity if you allow amortization. Is a heap with my requirements ruled out in the comparison model, or is that unknown? $\endgroup$ Mar 28 '14 at 17:15
  • $\begingroup$ I think you can not achieve it in the comparison model. I have updated my answer to reflect this. $\endgroup$ Mar 29 '14 at 14:20
  • $\begingroup$ 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. $\endgroup$ Mar 29 '14 at 18:49
  • $\begingroup$ I am not sure if and how constant time delete-key operations may affect the equivalence of priority queues and sorting. Perhaps you may ask the authors directly. However, despite the efforts, still we do not have any heap data structure matching your requirements. May be I am wrong, but I am still inclined to think that it can not be achieved for general deletions. $\endgroup$ Mar 29 '14 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.