2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

However, if you're trying to optimize the amount of work per deletion and for some reason the time taken to scan the array "doesn't count" (I don't understand why it wouldn't count, but let's just run with it):

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.

$\endgroup$
  • $\begingroup$ Why the scanning the array counts little: Consider the case that comparisons are much more costly than checking the deletion predicate. $\endgroup$ – Niels Möller May 5 '14 at 8:17
  • $\begingroup$ And deleting elements one by one gives a worst case cost of O(n log n), e.g, say k = n/3 or so. It would be nice to have a single good algorithm, and not have to select algorithm depending on the number of elements to be deleted (which might not even be known up front). One idea could be to scan the array from the start, delete elements one by one, but at the same time also trim elements at the end of the array. So that deletion in the middle of the heap never inserts another element which should be deleted. Should help a lot in case almost all elements should be deleted, at least. $\endgroup$ – Niels Möller May 5 '14 at 8:24
  • $\begingroup$ @NielsMöller Alternatively, you could have $O(n)$ space hash map. Delete $k$ elements and heapify in $O(k + \lg n)$ $\endgroup$ – John Strood Jul 26 '19 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.