二进制Min堆数据结构的实现

Question

在阅读了有关堆的内容之后，我尝试实现堆。下面是我的代码和测试。欢迎任何关于正确性、性能的反馈。

import java.util.Arrays;

public class BinaryHeap2 {
    private int[] heap;
    private int size;
    private int capacity;

    public BinaryHeap2(){
        capacity = 100;
        size = 0;
        heap = new int[capacity];
    }

    public BinaryHeap2(int capacity){
        this.capacity = capacity;
        size = 0;
        heap = new int[this.capacity];
    }

    public void offer(int i){

        if(size>=capacity){
            capacity = capacity*2;
            int[] tmp = new int[capacity];
            System.arraycopy(heap, 0, tmp, 0, heap.length);
            heap = tmp;
        }

        heap[size++] = i;

        heapifyUp(size-1);

    }

    private void heapifyUp(int position){
        int parent = (position-1)/2;
        while(heap[parent]>heap[position]){
            swap(parent,position);
            position = parent;
            parent = (position-1)/2;
        }
    }

    private void swap(int i, int j){
        int t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }

    public int peek(){
        return heap[0];
    }

    public int poll(){
        int min = heap[0];
        heap[0] = heap[size-1];
        size--;
        if(size>1)
            heapifyDown(0);
        return min;
    }

    public int getSize(){
        return size;
    }

    private void heapifyDown(int i) {
        int leftChild = 2*i+1;
        int rightChild = 2*i+2;
        int childToSwap = heap[leftChild]<heap[rightChild]?leftChild:rightChild;        
        while(heap[i]> heap[childToSwap]){
            swap(i,childToSwap);
            i = childToSwap;
            leftChild = 2*i+1;
            rightChild = 2*i+2;
            if(rightChild>=size||leftChild>=size)break;
            childToSwap = heap[leftChild]<heap[rightChild]?leftChild:rightChild;
        }

    }

    public void display(){
        System.out.println(Arrays.toString(heap));
    }


}

以下是单元测试

import static org.junit.Assert.assertEquals;

import org.junit.Before;
import org.junit.Test;

public class BinaryHeap2Test {

    BinaryHeap2 heap;
    @Before
    public void setUp(){
        heap = new BinaryHeap2(3);
    }

    @Test
    public void test() {
        heap.offer(7);
        heap.offer(6);
        heap.offer(3);
        heap.offer(2);
        heap.offer(1);
        heap.offer(5);
        heap.offer(4);
        heap.offer(3);
        heap.offer(2);  
        heap.display();
        assertEquals(1, heap.peek());
        assertEquals(heap.poll(), 1);
        assertEquals(heap.poll(), 2);
        assertEquals(heap.poll(), 2);
        assertEquals(heap.poll(), 3);
        assertEquals(heap.poll(), 3);
        assertEquals(heap.poll(), 4);
        heap.offer(1);
        heap.display();
        assertEquals(heap.poll(), 1);
        assertEquals(heap.poll(), 5);
        assertEquals(heap.poll(), 6);
        assertEquals(heap.poll(), 7);   
        heap.display();

    }

    @Test
    public void test2(){
        heap.offer(300);
        heap.offer(200);
        heap.offer(100);

        assertEquals(100, heap.poll());
        heap.display();
        assertEquals(200, heap.poll());
        heap.display();
        assertEquals(300, heap.poll());
        heap.display();
        heap.offer(2);
        assertEquals(2, heap.peek());
        heap.offer(100);
        heap.offer(1);
        heap.offer(5);
        assertEquals(1, heap.poll());
        assertEquals(2, heap.poll());
        assertEquals(5, heap.poll());
        assertEquals(100, heap.poll());
    }

}

Answer 1

• 构造函数中有重复的代码，默认构造函数应该调用另一个具有容量的构造函数。
• 也许可以使容量= 100常量，并将其命名为DEFAULT_INITIAL_CAPACITY。
• 你的测试没有名字。在阅读了一个测试的名称(或您通常命名的任何内容)之后，您应该对测试的内容有一定的了解。
• 你一次测试太多东西。一个测试应该测试代码的一个方面。您可以调用poll n次并断言peek值，然后轮询、提供和断言轮询值。最好是把它分开，分别测试民意测验和提供机制。所以实际上，第一部分可能会失败，而第二部分会没事，或者反过来。所以你永远无法确定到底是什么失败了。你也不需要多次调用报价，这不会有任何影响，对吗？如果是这样的话，它应该是一个单独的测试。
• test2()也没有意义，我的意思是，除了较大的数字之外，第一个测试的区别是什么？我肯定您想测试内部数组的大小调整，但是我们怎么知道呢？我会这样做：@Test void exceedingHeapsizeCapacityIncreaseHeapCapacity() { int heapCapacity = 1；BinaryHeap2堆=新BinaryHeap2(1)；heap.offer(1)；heap.offer(1)；// no断言，如果调整大小不能工作，第二次调用将引发异常.也许提供实际容量的方法不会是_that_坏}
• 在测试中调用“display”也是没有意义的，如果您在一个应用程序中有数千个测试，您只需在控制台中填充废话，使实际的故障排除更加困难，最好是在测试类中进行调试或跟踪调试并激活它，当您必须对测试或生产中的其他问题进行故障排除时。
• 该类型有一个“显示”方法。通常你有自己的“视图”类型。您只需传递您的Heap并告诉视图“显示您的内容”(如果您想要更改‘表示层’，比如，如果您想以html的形式在浏览器中显示它，类型就不能写html本身)
• 尽量避免命名像i和j这样的变量。如果你自己读方法交换，你不知道，i和j是什么意思，一个方法应该尽可能自我解释。要真正理解它，您必须检查一下，谁真正调用了这个方法。
• heapifyDown的意图并不十分清楚。我读了三遍，但仍然不明白--目标应该是，你可以读一次，理解它，不是吗？我认为在那种情况下这是可能的。时间循环中的中断很疼，你不能在时间条件下也这么做吗？
• 公共/私人方法的排序一直是人们讨论的话题。它通常是公开的，私下的。但我也喜欢按代码的调用方式排序。就像你有公开的无效报价，你打电话给heapifyUp，就在它下面，我真的很喜欢它。但是: getSize()可以移动到heapifyDown下面。

Answer 2

• heapifyDown测试循环中的子类存在，但在一开始就忽略了这个测试。如果size == 2，它将尝试访问一个不存在的正确的孩子。
• 类似地，循环可能会提前中断: if (rightChild>=size||leftChild>=size)中断；如果没有rightChild，则中断。但是，leftChild很可能存在，并且需要交换。
• childToSwap的计算看起来有些拥挤。考虑到上述特殊情况，将其分解为(私有)方法是值得的。
• 当size/capacity的比率低于某一阈值时，我会考虑缩小堆。