I have a binary min-heap, size n, and I want to delete a number of elements, ide

Question

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.

Explanation / Answer

I think you're optimizing for the wrong metrics. The total running time will be ?(n) no matter what you do. Scanning the entire array to identify which elements to remove will take ?(n) time, so your total running time can't be any better than ?(n). Conversely, there is a simple algorithm that achieves ?(n) time. MakeHeap can be done in ?(n) time, so it gives you a simple ?(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(lgn) time. So, if you want to delete k items, delete each one-by-one. Total running time: ?(n) to scan the array, ?(klgn) to delete them.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.