An algorithm to drop low-priority items from a heap-based priority queue

Question

I am looking for an efficient algorithm to drop from a complete binary min heap all items whose weight exceeds a given value. (Or, equivalently, to drop from a priority queue realised by such a heap all items whose priority is too low.)

It is easy to make an algorithm that walks the heap level by level from bottom up, comparing the item weights to the threshold value and doing dropping-and-swapping. It will turn out to be extremely inefficient though if, for example, all items in the heap need to be dropped.

It looks better to start by finding an item at the bottom level that is heavier than the threshold value and walk upwards from it until finding the highest element that needs to be dropped. Then the whole sub-heap under that element needs to be dropped. The space taken up by this sub-heap can be filled with elements moved from one or two bottom levels that are not in this sub-heap, and the sub-heap can be rebuilt. However, this method does not look perfect either, as most likely the dropped sub-heap will be filled with elements some of which need to be dropped too.

Are there any efficient or well-studied algorithms for this?

Answer 1

Let $n$ denote the size of the min-heap. It's easy to do this in linear time, i.e., $O(n)$ time: walk through the heap, copying over only the items that are below the threshold into an array; then call MakeHeap to turn it into a heap.

I would be surprised if you can do better than this, in asymptotic worst-case running time. For instance, any approach that involves scanning all items at the bottom layer will necessarily take at least linear time, i.e., at least $\Omega(n)$ time. And if there is any item in the bottom layer that you don't examine, then in at least some cases you won't be able to tell whether it needs to be included or not. So I suspect it may be possible to construct an adversarial argument that shows that at least $\Omega(n)$ time is needed -- though I don't know for sure.

Alternatively, one could consider the running time as a function of the output size. Let $m$ denote the size of the output, i.e., the number of elements that are above the threshold. Then it is easy to achieve $O(m)$ running time, by doing a top-down recursive pre-order traversal of the min-heap (think of it as a binary tree), truncating the traversal at each internal node that is above the threshold. The running time is $O(m)$ since you only visit a node if it is included in the output or if it is an immediate descendant of a node included in the output; since each node has at most 2 descendants, this means that the number of nodes visited is at most $3m$, i.e., $O(m)$. This is clearly optimal, as a function of output size: any algorithm that produces $m$ outputs has to take at least $\Omega(m)$ time, just to write out the output.