0

我正在尝试实现一个通用的二进制最小堆。我有一个代表堆的 minHeap 类和一个代表节点的嵌套 Node 类。所以 minHeap 由 Node 对象组成。Node 类有两个属性：一些通用数据和一个整数键。问题是，我一生都无法弄清楚如何比较两个 Node 类型的对象。我尝试在 Node 上实现 Icomparable，重载运算符：我无法让它工作。这是到目前为止的基本结构（我已经删除了不重要的部分）：

'''

public class MinHeap<T>
{

    static private int INITIAL_CAPACITY = 10;
    private Node[] heap = new Node[INITIAL_CAPACITY];

    private int heapSize = 0;
    private int heapCapacity = INITIAL_CAPACITY;

    private class Node
    {
        private T data;
        private int key;
    }
    ...

'''

我想要做的是重载运算符，例如 <、>、==，以便能够比较 minHeap 类方法中的节点。例如，当我在 minHeap 中插入一个新节点时，我需要将新节点的键与另一个节点的键进行比较。我怎么能做到这一点？

4

1 回答 1

2

唉，现在不可能实现一个简单的<=>运算符并拥有所有>, <, ==等运算符以及IComparable<Node>，IEquatable<Node>......我们必须编写大量的样板代码。

我建议实施

  public static int Compare(Node left, Node right)

比较两个Node实例的方法，然后您可以轻松设计所有其余的 oneliner：

  private class Node : IComparable<Node>, IEquatable<Node> {
    private T data;
    private int key;

    public static int Compare(Node left, Node right) {
      if (ReferenceEquals(left, right)) // we can't use == here
        return 0;
      if (left is null) // or ReferenceEquals(left, null) to avoid ==
        return -1;
      if (right is null)
        return 1;

      //TODO: return compare result
      //        negative if left < right, 
      //               0 if left == right 
      //        positive if left > right 
      return left.key.CompareTo(right.key);
    }

    //TODO: Check: I've assumed that comparison is key based
    public override int GetHashCode() => key;

    // A lot of boiler plate code below...
    public int CompareTo(Node other) => Compare(this, other);
    public bool Equals(Node other) => Compare(this, other) == 0;
    public override bool Equals(object obj) => obj is Node node && Equals(node);

    public static bool operator ==(Node left, Node right) => Compare(left, right) == 0;
    public static bool operator !=(Node left, Node right) => Compare(left, right) != 0;
    public static bool operator >=(Node left, Node right) => Compare(left, right) >= 0;
    public static bool operator > (Node left, Node right) => Compare(left, right) > 0;
    public static bool operator < (Node left, Node right) => Compare(left, right) < 0;
    public static bool operator <=(Node left, Node right) => Compare(left, right) <= 0;
  }
于 2021-10-16T08:24:59.477 回答