Min & Max堆实现

Question

如下所示，我使用用于存储元素的数组实现了Min和Max堆数据结构。我需要一个代码检查，拜托。请提供一般性实施建议，因为这些建议在我目前的要求中没有用。我已经记录了单元测试，我也分享了这些。

抽象类

public abstract class AbstractHeap
{
    #region internal properties
    private int Capacity { get; set; }
    internal int Size { get; set; }
    internal int[] Nodes { get; set; }
    #endregion

    #region constructors
    public AbstractHeap()
    {
        Capacity = 100;
        Size = 0;
        Nodes = new int[Capacity];
    }
    #endregion

    #region helperMethods
    public void EnlargeIfNeeded()
    {
        if (Size == Capacity)
        {
            Capacity = 2 * Capacity;
            Array.Copy(Nodes, Nodes, Capacity);
        }
    }

    public int getLeftChildIndex(int parentIndex)
    {
        return 2 * parentIndex + 1;
    }

    public bool hasLeftChild(int parentIndex)
    {
        return getLeftChildIndex(parentIndex) < Size;
    }

    public int leftChild(int index)
    {
        return Nodes[getLeftChildIndex(index)];
    }

    public int getRightChildIndex(int parentIndex)
    {
        return 2 * parentIndex + 2;
    }

    public bool hasRightChild(int parentIndex)
    {
        return getRightChildIndex(parentIndex) < Size;
    }

    public int rightChild(int index)
    {
        return Nodes[getRightChildIndex(index)];
    }

    public int getParentIndex(int childIndex)
    {
        return (childIndex - 1) / 2;
    }

    public bool hasParent(int childIndex)
    {
        return getParentIndex(childIndex) >= 0;
    }

    public int parent(int index)
    {
        return Nodes[getParentIndex(index)];
    }

    public void swap(int index1, int index2)
    {
        int temp = Nodes[index1];
        Nodes[index1] = Nodes[index2];
        Nodes[index2] = temp;
    }

    #endregion

    #region available public methods

    /// <summary>
    /// Gets the minimum element at the root of the tree
    /// </summary>
    /// <returns>Int value of minimum element</returns>
    /// <exception cref="">InvalidOperationException when heap is empty</exception>
    public int peek()
    {
        if (Size == 0)
            throw new InvalidOperationException("Heap is empty");

        return Nodes[0];
    }

    /// <summary>
    /// Removes the minimum element at the root of the tree
    /// </summary>
    /// <returns>Int value of minimum element</returns>
    /// <exception cref="">InvalidOperationException when heap is empty</exception>
    public int pop()
    {
        if (Size == 0)
            throw new InvalidOperationException("Heap is empty");

        int item = Nodes[0];
        Nodes[0] = Nodes[Size - 1];
        Size--;
        heapifyDown();
        return item;
    }

    /// <summary>
    /// Add a new item to heap, enlarging the array if needed
    /// </summary>
    /// <returns>void</returns>
    public void add(int item)
    {
        EnlargeIfNeeded();
        Nodes[Size] = item;
        Size++;
        heapifyUp();
    }
    #endregion

    #region abstract methods
    internal abstract void heapifyUp();
    internal abstract void heapifyDown();
    #endregion
}

使用抽象类

的

最大堆实现

public class MaxHeap : AbstractHeap
{
    #region constructors

    public MaxHeap() : base()
    {
    }
    #endregion

    #region internal methods
    internal override void heapifyDown()
    {
        int index = 0;
        while (hasLeftChild(index))
        {
            int largerChildIndex = getLeftChildIndex(index);
            if (hasRightChild(index) && rightChild(index) > leftChild(index))
            {
                largerChildIndex = getRightChildIndex(index);
            }

            if (Nodes[largerChildIndex] > Nodes[index])
                swap(index, largerChildIndex);
            else
                break;
            index = largerChildIndex;
        }
    }
    internal override void heapifyUp()
    {
        int index = Size - 1;

        while (hasParent(index) && parent(index) < Nodes[index])
        {
            swap(index, getParentIndex(index));
            index = getParentIndex(index);
        }
    }
    #endregion
}

使用抽象类

的

最小堆实现

public class MinHeap : AbstractHeap
{
    #region constructors
    public MinHeap() : base()
    {
    }
    #endregion

    #region internal methods
    internal override void heapifyDown()
    {
        int index = 0;
        while (hasLeftChild(index))
        {
            int smallerChildIndex = getLeftChildIndex(index);
            if (hasRightChild(index) && rightChild(index) < leftChild(index))
            {
                smallerChildIndex = getRightChildIndex(index);
            }

            if (Nodes[smallerChildIndex] < Nodes[index])
                swap(index, smallerChildIndex);
            else
                break;
            index = smallerChildIndex;
        }
    }
    internal override void heapifyUp()
    {
        int index = Size - 1;

        while (hasParent(index) && parent(index) > Nodes[index])
        {
            swap(index, getParentIndex(index));
            index = getParentIndex(index);
        }
    }
    #endregion
}

单元对最大堆

的测试

[TestClass]
public class MaxHeapTests
{
    [TestMethod]
    public void AddEmptyRemove()
    {
        var heap = new MaxHeap();

        heap.add(10);
        Assert.AreEqual(10, heap.peek());

        int result = heap.pop();
        Assert.AreEqual(10, result);
        heap.add(20);
        Assert.AreEqual(20, heap.peek());
    }

    [TestMethod]
    public void AddMultipleCheckPeek()
    {
        var heap = new MaxHeap();
        foreach (int item in new int[] { 10, 20, 2, 45, 7, 5, 12 })
            heap.add(item);
        Assert.AreEqual(heap.peek(), 45);
    }

    [TestMethod]
    public void AddMultipleCheckPopThenPeek()
    {
        var heap = new MaxHeap();
        foreach (int item in new int[] { 10, 20, 2, 45, 7, 5, 12 })
            heap.add(item);
        int result = heap.pop();
        Assert.AreEqual(45, result);
        Assert.AreEqual(20, heap.peek());
    }

    [TestMethod]
    [ExpectedException(typeof(InvalidOperationException))]
    public void PeekPoopEmpty()
    {
        var heap = new MaxHeap();
        heap.peek();
        heap.pop();
    }
}

单元对最小堆

的测试

[TestClass]
public class MinHeapTests
{
    [TestMethod]
    public void AddEmptyRemove()
    {
        var heap = new MinHeap();

        heap.add(10);
        Assert.AreEqual(10, heap.peek());

        int result = heap.pop();
        Assert.AreEqual(10, result);
        heap.add(20);
        Assert.AreEqual(20, heap.peek());
    }

    [TestMethod]
    public void AddMultipleCheckPeek()
    {
        var heap = new MinHeap();
        foreach (int item in new int[] { 10, 20, 2, 45, 7, 5, 12 })
            heap.add(item);
        Assert.AreEqual(heap.peek(), 2);
    }

    [TestMethod]
    public void AddMultipleCheckPopThenPeek()
    {
        var heap = new MinHeap();
        foreach (int item in new int[] { 10, 20, 2, 45, 7, 5, 12 })
            heap.add(item);
        int result = heap.pop();
        Assert.AreEqual(2, result);
        Assert.AreEqual(5, heap.peek());
    }

    [TestMethod]
    [ExpectedException(typeof(InvalidOperationException))]
    public void PeekPoopEmpty()
    {
        var heap = new MinHeap();
        heap.peek();
        heap.pop();
    }
}

Answer 1

公共抽象类AbstractHeap { #region内部属性私有int容量{ get；set；}内部int大小{ get；set；}内部int[]节点{ get；set；}

Capacity似乎没有任何用处。它仅仅是Nodes.Length的镜像，是bug的潜在来源。

为什么子类应该能够访问Size和Nodes的设置程序？我觉得他们应该是私人的。

public void EnlargeIfNeeded() { if (Size == Capacity) { Capacity = 2 \* Capacity; Array.Copy(Nodes, Nodes, Capacity); } }

这是婴儿车。添加一个单元测试，它将100个以上的元素插入堆中，观察它变红，然后修复它。

public int getLeftChildIndex(int parentIndex) { return 2 \* parentIndex + 1; } public bool hasLeftChild(int parentIndex) { return getLeftChildIndex(parentIndex) < Size; } public int leftChild(int index) { return Nodes[getLeftChildIndex(index)]; }

不使用表达式值方法有什么特别的原因吗？

有什么特别的原因不遵循标准的C#风格和使用UpperCamelCase的方法名称吗？

在我看来，为左、右和父方法各有三种方法似乎有点过分，但这是一个风格问题，我可以看到一个论点，即它是用于To和downheap堆方法的可读性的。另一方面，为什么所有这些方法(和Swap)都是public？这暴露了太多的内部实现。

internal abstract void heapifyUp(); internal abstract void heapifyDown();

我真的不明白为什么要两次实现这些方法，它们是整个类中最复杂的方法。我更愿意在基类中实现它们一次，并通过IComparer字段或抽象方法Compare(int a, int b)来处理这些差异。