Searching for and removing a low priority item in an array

Question

Suppose you are handed a list of n events, each carrying some priority value represented by a real number in the interval [0,1], where a larger priority corresponds to a more important event. This list is represented by an array that allows you to specify an event index i and instantly grab the event information at position i. Sometimes, an event manager is handed a new event to add to the list. The list can only have n events, so to add an event requires removing an event first.

Suppose we wish to remove events whose priority is low, meaning in the bottom 50% of priority values, and we wish to do this removal in O(1) time. What is an algorithm that can achieve this goal?

Answer 1

I propose a randomized algorithm to tackle this problem. We wish to find an element with priority in the bottom 50% of priority values that exist within our array of events. If we were to randomly choose an event from the array, this would imply we will choose a low priority event with probability 1/2. So what we can do is randomly choose an element k times and keep the element after each sample that has the lowest priority.

The probability we do not find a low priority element is equal to the probability that none of our samples are a low priority element. In particular, the probability of this event is equal to (1/2)^k. For a constant value of k, we will have an O(1) algorithm that successfully finds a low priority element with probability equal to 1 - (1/2)^k. For example, choosing k = 10 gives us that we find a low priority element with probability equal to roughly 0.999 using O(1) time.