0

我有不到一周的面试的在线评估部分。问题是：我最擅长的语言是 C#，它没有内置的堆或优先级队列实现。随着在线评估的进行，问题的最佳解决方案可能需要这些数据结构之一。虽然我过去有过一些其他语言的经验（例如 Java、Python），但我还没有准备好接受他们的面试；考虑到面试的时间框架，我想坚持使用 C#。

对于面对面的面试，这不是问题，因为我只能提到 C# 没有这个功能，并假设一个现成的Heap或PriorityQueue类（实际上，.NET 6 预览版有一个PriorityQueue实现，但在线评估平台肯定没有这个支持）。

鉴于这一切，我决定最好的做法是编写一个最小的MinPriorityQueue实现，可以将其复制粘贴到最佳解决方案需要这种数据结构的在线评估中。然后我可以在评论中提及这段代码的来源，以及我复制粘贴它的原因。

我希望这个实现尽可能轻量级，但仍然足够灵活，可以用于诸如排序矩阵中的第 K 个最小元素或合并 k 个排序列表之类的问题。灵活，我的意思是能够在没有任何/很多修改的情况下使用典型的 LeetCode 类型的问题。轻量级是指使用尽可能少的空间为快速执行而优化。

这是我到目前为止所得到的。关于提高性能的任何提示？谢谢！

public class MinPriorityQueue<T>
{
    private readonly List<(T Element, int Priority)> items;

    public MinPriorityQueue(int initialCapacity)
    {
        this.items = new List<(T, int)>(initialCapacity);
    }

    public void Add(T element, int priority)
    {
        this.items.Add((element, priority));
        this.BubbleUp(this.items.Count - 1);
    }

    public T RemoveMin()
    {
        if (this.items.Count == 0) return default;

        var minElement = this.items[0].Element;
        var endIndex = this.items.Count - 1;

        this.items[0] = this.items[endIndex];
        this.items.RemoveAt(endIndex);

        this.BubbleDown(index: 0);

        return minElement;
    }

    private void BubbleDown(int index)
    {
        var leftChildIndex = 2 * index + 1;
        var rightChildIndex = 2 * index + 2;
        var maxIndex = this.items.Count - 1;

        if (leftChildIndex > maxIndex)
        {
            return;
        }

        if (rightChildIndex > maxIndex)
        {
            if (this.items[index].Priority > this.items[leftChildIndex].Priority) this.SwitchPlaces(index, leftChildIndex);

            return;
        }

        if (this.items[index].Priority < this.items[leftChildIndex].Priority
            && this.items[index].Priority < this.items[rightChildIndex].Priority)
        {
            return;
        }

        var indexForSwap = this.items[leftChildIndex].Priority < this.items[rightChildIndex].Priority 
            ? leftChildIndex 
            : rightChildIndex;

        this.SwitchPlaces(index, indexForSwap);
        this.BubbleDown(indexForSwap);
    }

    private void BubbleUp(int index)
    {
        int parentIndex = (index - 1) / 2;

        if (parentIndex < 0) return;

        if (this.items[index].Priority >= this.items[parentIndex].Priority) return;

        this.SwitchPlaces(index, parentIndex);
        this.BubbleUp(parentIndex);
    }

    private void SwitchPlaces(int first, int second)
    {
        var temp = this.items[first];
        this.items[first] = this.items[second];
        this.items[second] = temp;
    }
}
4

0 回答 0