Program.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace FastWeightedSelect
{
    class Program
    {
        struct Element
        {
            public int Size;
            public int Value;
            public override string ToString()
            {
                return $"Size: {Size}, Value: {Value}";
            }
        }
        static List<int> usedTimes = new List<int>();

        // This demostrates how to get the $k$ elements with the smallest "Value" such that that total "Size" exceeds a certain threshold.
        static void Main(string[] args)
        {
            // Generate some test data. The algorithm currently does not like elements with the same "time"

            static int randomTime(Random random)
            {
                while (true)
                {
                    int r = random.Next(100, 1000000);
                    if (!usedTimes.Contains(r))
                    {
                        usedTimes.Add(r);
                        return r;
                    }
                }
            }
            List<Element> testElements = new List<Element>();
            Random random = new Random();
            for (int i = 0; i < 100000; i++)
            {
                // Most inefficient way to generate test data.
                testElements.Add(new Element { Size = random.Next(100, 100000), Value = randomTime(random) });
            }

            long toRemove = 500_000_000;

            // Find the last element to remove
            Element lastToRemove = (Element)FindKThElement(testElements.ToArray(), toRemove);

            // Filter all elements to remove
            List<Element> toEvict = testElements.Where(e => e.Value <= lastToRemove.Value).ToList();

            // Total space freed
            Console.WriteLine($"To evict: {toRemove}, evicted: {toEvict.Sum(e => (long)e.Size)}");
        }

        // The algorithm is basically quicksort. But in the recursive step we only need to recuse in one of the subtrees. And we can figure out in linear time which one it is. This is why the expected running time is O(n)
        private static Element? FindKThElement(Span<Element> testElements, long size)
        {
            // Special cases
            if (testElements.Length == 0)
            {
                return null;
            }
            if (testElements.Length == 1)
            {
                return testElements[0];
            }

            // The same partition step as in quicksort
            int pivot_loc = Partition(testElements);

            var pivot = testElements[pivot_loc];

            // Figure out how much space all elements with a value that is at most the one of the pivot take up
            long pivotPosition = testElements.ToArray().Where(e => e.Value <= pivot.Value)
                                             .Sum(e => (long)e.Size);

            // If the space is exactly the right amount we are done
            if (pivotPosition == size)
            {
                // VERY coincidental.
                return pivot;
            }

            // If the space is too large, then we know that we have to recurse into the left child. That way we can cut off roughly half of the elements.
            else if (pivotPosition > size)
            {
                var result = FindKThElement(testElements.Slice(0, pivot_loc + 1), size);
                if (result == null)
                    return pivot;
                return result;
            }
            // If the pivot was too small then we only have to search in the right child. Because we know that all of the elements up to the pivot have to be removed. We have to make sure that the size to look for in the right tree is reduced
            // by the space of the elements on the left together with the pivot
            else // if (pivotPosition < size)
            {
                // The pivot was chosen too small
                return FindKThElement(testElements.Slice(pivot_loc + 1), size - pivotPosition);
            }
        }

        // To find random pivot elements. Required to get the running time.
        static Random kRandom = new Random();

        // The QuickSort partition algorithm.
        private static int Partition(Span<Element> input)
        {
            int pivotIndex = kRandom.Next(0, input.Length);
            Swap(input, pivotIndex, input.Length - 1);
            Element pivot = input[input.Length - 1];
            int wallindex = 0;
            for (int currentindex = 0; currentindex < input.Length - 1; ++currentindex)
            {
                if (input[currentindex].Value < pivot.Value)
                {
                    Swap(input, wallindex, currentindex);
                    ++wallindex;
                }
            }
            Swap(input, wallindex, input.Length - 1);
            return wallindex;
        }

        private static void Swap(Span<Element> ar, int a, int b)
        {
            var temp = ar[a];
            ar[a] = ar[b];
            ar[b] = temp;
        }
    }
}