Is it possible to implement extractMin on a Max-Heap in O(log(n)) time, and if so how? Or do you need a more elaborate structure like a max-min heap?
3
-
$\begingroup$ You can use an adversary argument to show that in extreme situations, you have to check the values of all leaves before you can tell the value of the minimum element. $\endgroup$– Yuval FilmusCommented Feb 10, 2018 at 20:21
-
$\begingroup$ so by this you mean that it is impossible to do it in O(log(n)) time? Do i then need a min-max heap or what? $\endgroup$– sssCommented Feb 11, 2018 at 10:47
-
$\begingroup$ You cannot do it with a max-heap. There are probably several other ways to do it. $\endgroup$– Yuval FilmusCommented Feb 11, 2018 at 14:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Suppose that there is an algorithm that examines a complete max-heap (i.e. one in which all leaves have the same depth) and outputs the minimum without accessing all leaves. Whenever the algorithm examines the value of an internal node, hand it the value 2, and whenever it examines the value of a leaf, hand it the value 1. The algorithm misses at least one leaf $\ell$, and so cannot tell the situation in which all leaves have the value 1 from the situation in which all leaves but $\ell$ have the value 1, and $\ell$ has the value 0.
answered Feb 10, 2018 at 20:24