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.

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Geoffrey Irving
    Mar 28, 2014 at 17:15
  • $\begingroup$ I think you can not achieve it in the comparison model. I have updated my answer to reflect this. $\endgroup$
    – Massimo Cafaro
    Mar 29, 2014 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$
    – Geoffrey Irving
    Mar 29, 2014 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$
    – Massimo Cafaro
    Mar 29, 2014 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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