1
$\begingroup$

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?

$\endgroup$
  • $\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 Filmus Feb 10 '18 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$ – sss Feb 11 '18 at 10:47
  • $\begingroup$ You cannot do it with a max-heap. There are probably several other ways to do it. $\endgroup$ – Yuval Filmus Feb 11 '18 at 14:17
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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