0
$\begingroup$

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.

$\endgroup$
5
  • 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
    Nov 30, 2022 at 11:40
  • $\begingroup$ A balanced BST(like AVL tree, or even RB tree) would do the trick. $\endgroup$
    – Rinkesh P
    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
    Nov 30, 2022 at 12:27
  • $\begingroup$ @Nathaniel ah yes, misinterpreted the notations. $\endgroup$
    – Rinkesh P
    Dec 1, 2022 at 4:51
  • $\begingroup$ @Russel yes i mean max. $\endgroup$
    – Rma
    Dec 1, 2022 at 11:12

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ Of course, the bound can be beaten for specific kinds of keys (e.g. strings and integers). $\endgroup$
    – Pseudonym
    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
    Nov 30, 2022 at 14:05
  • $\begingroup$ Thanks for the answer, if input numbers are labeled from 1 to $n$ then? $\endgroup$
    – Rma
    Dec 1, 2022 at 11:11
  • 1
    $\begingroup$ @Rma Using the same name $n$ for bound and for size of the structure is not wise. See here for some ideas. $\endgroup$
    – Nathaniel
    Dec 1, 2022 at 11:22
2
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ $O(\log n)$ is not the same as $o(\log n)$ $\endgroup$
    – Dmitry
    Dec 13, 2022 at 8:01

Your Answer

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

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