0
$\begingroup$

Is it possible to find the nodes larger than $ k $ in a min-max heap in $ O(m) $ time, where $ m $ is the number of nodes larger than $ k $?

If it is possible, then how do I implement the rest of the standard heap procedures in standard time (insert and delete, extract min and extract max is easy obviously)?


If needed the whole problem statement goes like this:

We want to add operation to our (max) priority queue. We are interested in adding the following operation. Below, x and y are objects and x.key and y.key are their keys in the priority queue (the objects can also have other satellite data). If an implementation of the priority queue is done as in CLRS, chapter 6, then the table can be a table of objects – not numbers; in that case x and y can have an attribute i, so that x.i and y.i denote their places (indices) in the table.

  • REMOVELARGEST(m): remove the m largest elements in the heap
  • DELETE(x): remove the element x from the heap.
  • FUSION(x,y): remove x and y from the heap and add the element z with key x.key+y.key
  • EXTRACTMIN: remove and return the element with the smallest key

  1. Expand the priority queue to support REMOVELARGEST(m) in $ O(m*log(n)) $ time.
  2. Expand the priority queue to support DELETE and FUSION in $ O(log(n)) $ time
  3. Expand the priority queue to support FINDLARGEST(k) in $ O(m) $ time, where $ m $ is the number of elements $ >=k $.
  4. Expand the priority queue to support EXTRACTMIN in $ O(log(n)) $ time.
$\endgroup$
  • 2
    $\begingroup$ You've been asking a lot of questions about the same problem lately. Don't forget we won't be available during your final exams. $\endgroup$ – Yuval Filmus Feb 11 '18 at 22:03
  • $\begingroup$ Please credit the source of all copied material. See cs.stackexchange.com/help/referencing $\endgroup$ – D.W. Feb 12 '18 at 16:47
1
$\begingroup$

You can use a max-heap and a min-heap containing the same elements, with pointers joining pairs of identical elements in both heaps. This allows supporting all the usual operations in logarithmic time, and the new operation (finding all nodes larger or smaller than a given value) in time linear in the output size.

$\endgroup$
  • $\begingroup$ Yes, i also thought of this. Thing is, i need to do it with one heap. I assumed it might be possible with a min-max heap but i cant figure out how. Do you think it is impossible achieve those runtimes with just one heap? $\endgroup$ – sss Feb 12 '18 at 2:27
  • $\begingroup$ I've never heard of a min-max heap. Please include all relevant details in the problem statement. $\endgroup$ – Yuval Filmus Feb 12 '18 at 5:09
  • $\begingroup$ Reading the problem statement over again i realized it actually doesnt state explicitly that only one heap must be used. Pretty stupid of me to rush to conclusion before having read it properly. I added the whole problem statement, including all the other question related to the problem, above $\endgroup$ – sss Feb 12 '18 at 13:44

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.