尝试实现最近邻搜索的优先级队列

Question

所以先介绍一下背景：

我正在尝试使用最近邻搜索实现 k-d 树。
为了实现 NN 搜索，我需要创建一个优先级队列。
优先队列必须有点坐标和距离。
所以我决定将这两个分组到一个元组中。

原来 C# 与我习惯的其他语言有点不同。

这是我在执行此操作时收到的错误消息：

PriorityQueue<Tuple<Point, double>> pq = new PriorityQueue<Tuple<Point, double>>();

error CS0311: The type System.Tuple<Tree.Point,double>' cannot be used as type parameterT' in the generic type or method PriorityQueue.PriorityQueue<T>'. There is no implicit reference conversion fromSystem.Tuple' to `System.IComparable>'

我对此研究了很长一段时间，但由于我是 C# 的新手，所以我不太明白为什么会这样。我想 Python 中的编程让生活变得非常轻松。

我的优先级队列 class 如下所示：

public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> dataHeap;

    public PriorityQueue()
    {
        this.dataHeap = new List<T>();
    }

    public void Enqueue(T value)
    {
        this.dataHeap.Add(value);
        BubbleUp();
    }

    public T Dequeue()
    {
        if (this.dataHeap.Count <= 0)
        {
            throw new InvalidOperationException("Cannot Dequeue from empty queue!");
        }

        T result = dataHeap[0];
        int count = this.dataHeap.Count - 1;
        dataHeap[0] = dataHeap[count];
        dataHeap.RemoveAt(count);
        ShiftDown();

        return result;
    }

    private void BubbleUp()
    {
        int childIndex = dataHeap.Count - 1;

        while (childIndex > 0)
        {
            int parentIndex = (childIndex - 1) / 2;

            if (dataHeap[childIndex].CompareTo(dataHeap[parentIndex]) >= 0)
            {
                break;
            }

            SwapAt(childIndex, parentIndex);
            childIndex = parentIndex;
        }
    }

    private void ShiftDown()
    {
        int count = this.dataHeap.Count - 1;
        int parentIndex = 0;

        while (true)
        {
            int childIndex = parentIndex * 2 + 1;
            if (childIndex > count)
            {
                break;
            }

            int rightChild = childIndex + 1;
            if (rightChild <= count && dataHeap[rightChild].CompareTo(dataHeap[childIndex]) < 0)
            {
                childIndex = rightChild;
            }
            if (dataHeap[parentIndex].CompareTo(dataHeap[childIndex]) <= 0)
            {
                break;
            }

            SwapAt(parentIndex, childIndex);
            parentIndex = childIndex;
        }
    }

    public T Peek()
    {
        if (this.dataHeap.Count == 0)
        {
            throw new InvalidOperationException("Queue is empty.");
        }

        T frontItem = dataHeap[0];
        return frontItem;
    }

    public int Count()
    {
        return dataHeap.Count;
    }

    /// <summary>Removes all elements from the queue.</summary>
    public void Clear()
    {
        this.dataHeap.Clear();
    }

    public void CopyToArray(T[] array, int index)
    {
        if (array == null)
        {
            throw new ArgumentNullException("Array");
        }

        int length = array.Length;
        if (index < 0 || index >= length)
        {
            throw new IndexOutOfRangeException("Index must be between zero and array length.");
        }
        if (length - index < this.dataHeap.Count-1)
        {
            throw new ArgumentException("Queue is bigger than array");
        }

        T[] data = this.dataHeap.ToArray();
        Array.Copy(data, 0, array, index, data.Length);
    }

    public bool IsConsistent()
    {
        if (dataHeap.Count == 0)
        {
            return true;
        }

        int lastIndex = dataHeap.Count - 1; 
        for (int parentIndex = 0; parentIndex < dataHeap.Count; ++parentIndex) 
        {
            int leftChildIndex = 2 * parentIndex + 1; 
            int rightChildIndex = 2 * parentIndex + 2;

            if (leftChildIndex <= lastIndex && dataHeap[parentIndex].CompareTo(dataHeap[leftChildIndex]) > 0)
            {
                return false;
            }
            if (rightChildIndex <= lastIndex && dataHeap[parentIndex].CompareTo(dataHeap[rightChildIndex]) > 0)
            {
                return false;
            }
        }

        return true;
    }

    private void SwapAt(int first,int second)
    {
        T value = dataHeap[first];
        dataHeap[first] = dataHeap[second];
        dataHeap[second] = value;
    }

    public override string ToString()
    {
        string queueString = string.Join(" ", dataHeap.ToArray());
        return queueString;
    }
}

我的观点class：

class Point : IComparable
{
    private double x;
    private double y;

    public Point(double xCoord, double yCoord)
    {
        SetPoint(xCoord, yCoord);
    }

    ~Point() {}

    public int CompareTo(object obj) 
    {
        if (obj == null) return 1;

        Point p = obj as Point;
        if (p != null) 
            return (this.x.CompareTo(p.x) & this.y.CompareTo(p.y));
        else 
           throw new ArgumentException("Object is not a Point");
    }

    public static bool operator ==(Point a, Point b)
    {
        if (ReferenceEquals(a, null) || ReferenceEquals(b, null)) return true;
        if (a[0] == b[0] && a[1] == b[1]) return true;
        else return false;
    }

    public static bool operator !=(Point a, Point b)
    {
        if (ReferenceEquals(a, null) || ReferenceEquals(b, null)) return true;
        if (a[0] != b[0] || a[1] != b[1]) return true;
        else return false;
    }

    public double this[int index]
    {
        get
        {
            if (index == 0) return x;
            else if (index == 1) return y;
            else throw new System.IndexOutOfRangeException("index " + index + " is out of range");
        }
        set
        {
            if (index == 0) x = value;
            else if (index == 1) y = value;
            else throw new System.IndexOutOfRangeException("index " + index + " is out of range");
        }

    }

    public void SetPoint(double xCoord, double yCoord)
    {
        x = xCoord;
        y = yCoord;
    }

    public override string ToString()
    {
        return "(" + x + ", " + y + ")";
    }
}

Answer 1

我建议您删除 T 上的约束，然后在 PriorityQueue 的构造函数中显式 IComparer<T>。如果提供 none，您现有的构造函数可以提供 Comparer<T>.Default 作为比较器。

然后您需要在整个 PriorityQueue 期间将 obj.CompareTo(other) 更改为 comp.Compare(obj, other)。

public class PriorityQueue<T>
{
    private List<T> dataHeap;
    private readonly IComparer<T> comp;

    public PriorityQueue() : this(Comparer<T>.Default) {}

    public PriorityQueue(IComparer<T> comp)
    {
        this.dataHeap = new List<T>();
        this.comp = comp;
    }
    ...
    private void BubbleUp() {
        if (this.comp.Compare(dataHeap[childIndex], dataHeap[parentIndex]) >= 0)
   }
}

尝试实现最近邻搜索的优先级队列

Trying to implement priority queue for nearest neighbor search

c#

generics

tree

tuples

nearest-neighbor