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?