<p>To the best of my knowledge, no heap data structure matches your requirements. In terms of complexity, the best one is the <a href="http://en.wikipedia.org/wiki/Brodal_queue" rel="nofollow noreferrer">Brodal queue</a>, 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.</p>

<p>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 <a href="https://cs.stackexchange.com/questions/6455/an-efficient-data-structure-supporting-insert-delete-and-mostfrequent/6462#6462">this question</a>.</p>

CC BY-SA 3.0
2014-03-28T17:15:34.523Z
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?
Geoffrey Irving
CC BY-SA 3.0
2014-03-29T14:20:52.103Z
I think you can not achieve it in the comparison model. I have updated my answer to reflect this.
Massimo Cafaro
CC BY-SA 3.0
2014-03-29T18:49:27.473Z
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.
Geoffrey Irving
CC BY-SA 3.0
2014-03-29T20:06:22.190Z
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.
Massimo Cafaro
CC BY-SA 3.0
2014-03-28T17:09:09.420Z
2014-03-29T14:29:55.323Z
2017-04-13T12:48:30.830Z
Massimo Cafaro
<p>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.</p>

<p>This data structure would be necessary to fix my broken answer to this question: <a href="https://cstheory.stackexchange.com/questions/21730/nontrivial-algorithm-for-computing-a-sliding-window-median/21744#21744">Nontrivial algorithm for computing a sliding window median</a>.</p>

CC BY-SA 3.0
2014-03-28T02:00:00.883Z
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.
jbapple
CC BY-SA 3.0
2014-03-28T15:20:04.387Z
Yes, $\Theta(\log n)$ find-min is fine for my purposes.  I'll update the question to clarify.
Geoffrey Irving
<ds.data-structures><sorting>
Heap with $O(1)$ delete-key
Geoffrey Irving
# Heap with $O(1)$ delete-key

(Asked by: username_0 on 2014-03-27)

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](https://cstheory.stackexchange.com/questions/21730/nontrivial-algorithm-for-computing-a-sliding-window-median/21744#21744).

**Tags:** ds.data-structures, sorting

> **Comments:**
> **username_1**: 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.  
> **username_0**: Yes, $\Theta(\log n)$ find-min is fine for my purposes.  I'll update the question to clarify.  

---

## 1 answers

### Answer by username_2 on 2014-03-28. Score: 2

To the best of my knowledge, no heap data structure matches your requirements. In terms of complexity, the best one is the [Brodal queue](http://en.wikipedia.org/wiki/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](https://cs.stackexchange.com/questions/6455/an-efficient-data-structure-supporting-insert-delete-and-mostfrequent/6462#6462).

> **Comments:**
> **username_0**: 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?  
> **username_2**: I think you can not achieve it in the comparison model. I have updated my answer to reflect this.  
> **username_0**: 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.  
> **username_2**: 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.  

---

