# What's a good algorithm for deleting multiple elements in a heap?

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.

I think you're optimizing for the wrong metrics. The total running time will be $\Theta(n)$ no matter what you do. Scanning the entire array to identify which elements to remove will take $\Theta(n)$ time, so your total running time can't be any better than $\Theta(n)$. Conversely, there is a simple algorithm that achieves $\Theta(n)$ time. MakeHeap can be done in $\Theta(n)$ time, so it gives you a simple $\Theta(n)$ running time algorithm: scan the entire array, delete whatever you want to delete, then run MakeHeap.
In this case there is an alternative algorithm. Deleting a single element from a heap can be done in $O(\lg n)$ time. So, if you want to delete $k$ items, delete each one-by-one. Total running time: $\Theta(n)$ to scan the array, $\Theta(k \lg n)$ to delete them.
• @NielsMöller Alternatively, you could have $O(n)$ space hash map. Delete $k$ elements and heapify in $O(k + \lg n)$ – John Strood Jul 26 '19 at 11:37