# Maximum, delete and insert fastest data structure

The runtime to find a max element in max heap is $$O(1)$$. It takes $$O(\log n)$$ time to delete an element and $$O(\log n)$$ time to insert a new element in the heap.

Does there exists a data structure in which max element can be found in $$o(\log n)$$ and still the time to delete is $$o(\log n)$$ and $$o(\log n)$$ time to insert a new element?

$$n$$ denotes the number of elements.

• Do you mean "... find a max element in a max heap..." and also, are those running-time worst-case or amortized? Commented Nov 30, 2022 at 11:40
• A balanced BST(like AVL tree, or even RB tree) would do the trick. Commented Nov 30, 2022 at 11:55
• @RinkeshP Complexities would not be $o(\log n)$ in a balanced BST. More like $\Theta(\log n)$ for deletion and insertion and $\mathcal{O}(\log n)$ for look up. Commented Nov 30, 2022 at 12:27
• @Nathaniel ah yes, misinterpreted the notations. Commented Dec 1, 2022 at 4:51
• @Russel yes i mean max.
– Rma
Commented Dec 1, 2022 at 11:12

You cannot create a data structure that guarantee $$o(\log n)$$ time for insertion AND $$o(\log n)$$ for maximum extraction, be it worst, amortized or average case.

The reason is that such a data structure would allow comparison sorting in $$o(n \log n)$$, which is theoretically not possible.

• Of course, the bound can be beaten for specific kinds of keys (e.g. strings and integers). Commented Nov 30, 2022 at 14:03
• Yes of course! If some hypotheses are made on keys, such complexities can be improved. For example, if keys are integers within known bounds, $\mathcal{O}(1)$ for insertion and deletion may be possible. Commented Nov 30, 2022 at 14:05
• Thanks for the answer, if input numbers are labeled from 1 to $n$ then?
– Rma
Commented Dec 1, 2022 at 11:11
• @Rma Using the same name $n$ for bound and for size of the structure is not wise. See here for some ideas. Commented Dec 1, 2022 at 11:22

Just to add to the previous answer, you can get $$O(1)$$ amortized bound for find, insert, and delete with some limitations with soft-heap [wiki, original paper, simplified implementation]. This heap can break the lower-bound for sorting by allowing some kind of corruptions to the keys.

Corruption means the soft-heap will make changes to keys of certain items in the heap so that multiple items will share a common key, without any means of retrieving the original keys. The number of corrupted keys can be controlled by a paremeter $$\varepsilon$$ such that it is guaranteed that at most $$\varepsilon n$$ are corrupted. Despite this seemingly unusual implementation it has applications for MST and linear-time selection.

Data structure that can be used for the aforementioned situation :

AVL tree : The self-balancing feature of AVL tree guarantees the performance of O(logN) in the worst case for all operations, including insertion, deletion, and searching.

Disadvantage of AVL tree : It's a complex data structure. if the program involves frequent insertion and deletion of elements then one should rather use red-black tree to avoid multiple rotations.

• $O(\log n)$ is not the same as $o(\log n)$ Commented Dec 13, 2022 at 8:01