I have a binary min-heap, size n, and I want to delete a number ofelements, 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 ofmoves of elements, and the number of additional tests of thepredicate.One possible way is to first delete elements from the correspondingarray, 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 asfar as I understand, the rebuild step can need n moves of elementseven if only one or two elements are deleted, if they are at unluckypositions in the array.I wonder if there's some good algorithm whichneeds O(n) element moves in the worst caseneeds few extra tests of the predicate, say total n + O(log n) testsin the worst caseneeds a lot fewer then n element moves in the special cases thatonly a few elements are deleted, or only a few elements are kept.
What's a good algorithm for deleting multiple elements in a heap?
heaps