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.
-
2$\begingroup$ Do you mean "... find a max element in a max heap..." and also, are those running-time worst-case or amortized? $\endgroup$Russel– Russel2022年11月30日 11:40:03 +00:00Commented Nov 30, 2022 at 11:40
-
$\begingroup$ A balanced BST(like AVL tree, or even RB tree) would do the trick. $\endgroup$Rinkesh P– Rinkesh P2022年11月30日 11:55:51 +00:00Commented Nov 30, 2022 at 11:55
-
2$\begingroup$ @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. $\endgroup$Nathaniel– Nathaniel2022年11月30日 12:27:11 +00:00Commented Nov 30, 2022 at 12:27
-
$\begingroup$ @Nathaniel ah yes, misinterpreted the notations. $\endgroup$Rinkesh P– Rinkesh P2022年12月01日 04:51:09 +00:00Commented Dec 1, 2022 at 4:51
-
$\begingroup$ @Russel yes i mean max. $\endgroup$Rma– Rma2022年12月01日 11:12:01 +00:00Commented Dec 1, 2022 at 11:12
3 Answers 3
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.
-
2$\begingroup$ Of course, the bound can be beaten for specific kinds of keys (e.g. strings and integers). $\endgroup$2022年11月30日 14:03:11 +00:00Commented Nov 30, 2022 at 14:03
-
$\begingroup$ 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. $\endgroup$Nathaniel– Nathaniel2022年11月30日 14:05:12 +00:00Commented Nov 30, 2022 at 14:05
-
$\begingroup$ Thanks for the answer, if input numbers are labeled from 1 to $n$ then? $\endgroup$Rma– Rma2022年12月01日 11:11:01 +00:00Commented Dec 1, 2022 at 11:11
-
1
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.
-
3$\begingroup$ $O(\log n)$ is not the same as $o(\log n)$ $\endgroup$Dmitry– Dmitry2022年12月13日 08:01:42 +00:00Commented Dec 13, 2022 at 8:01