I have a binary min-heap, size n, and I want to delete a number of elements, identified by some predicate.
Any algorithm needs at least n tests of the predicate (preferably, exactly n), so the interesting performance metrics are the number of moves of elements, and the number of additional tests of the predicate.
One possible way is to first delete elements from the corresponding array, using a single pass to delete elements and compact the array. And then rebuild the heap from the array. Both steps are O(n). But as far as I understand, the rebuild step can need n moves of elements even if only one or two elements are deleted, if they are at unlucky positions in the array.
I wonder if there's some good algorithm which
needs O(n) element moves in the worst case
needs few extra tests of the predicate, say total n + O(log n) tests in the worst case
needs a lot fewer then n element moves in the special cases that only a few elements are deleted, or only a few elements are kept.