使用 Comparable 接口创建最小堆

Question

我在添加我的字符串以创建最小堆时遇到问题。当我调试我的代码时，我相信我在添加 'B' 时遇到了问题，但是我运行进入了一个打印出 null.

的无限循环

这是我的字符串：

    String[] s = {"D", "F", "I", "C", "H", "A", "E", "J", "B", "G"};

添加方法：

public void add(Comparable newEntry) {
    int newIndex = ++lastIndex;
    int parentIndex = newIndex / 2;
    while ((newIndex > 1) && newEntry.compareTo(heap[parentIndex]) < 0) {
        heap[newIndex] = heap[parentIndex];
        newIndex = parentIndex;
        parentIndex = newIndex / 2;
    } // end while
    heap[newIndex] = newEntry;
} // end add

还有我的构造函数：

public MinHeap() {
        heap = new Comparable[DEFAULT_MAX_SIZE];
        lastIndex = 0;
    } // end default constructor
    public MinHeap(int maxSize) {
        heap = new Comparable[maxSize];
        lastIndex = 0;
    } // end constructor
    public MinHeap(Comparable[] entries) {
        lastIndex = entries.length;
        heap = new Comparable[lastIndex + 1];
        // copy given array to data field
        for (int index = 0; index < entries.length; index++)
            heap[index+1] = entries[index];
        // create heap
        for (int index = heap.length/2; index > 0; index--)
            reheap(index);
    } // end constructor

我的代码的驱动程序：

public class MinHeapDriver {
    public static void main(String[] argv)  {
      MinHeap aHeap = createMinHeap();
      testMinHeapOperations(aHeap);
    }  // end main   

   public static MinHeap createMinHeap() {
        MinHeap aHeap = new MinHeap();  
      String[] s = {"D", "F", "I", "C", "H", "A", "E", "J", "B", "G"};
        System.out.println("Testing add()");
      for (int i=0; i < s.length; i++) {
         System.out.print(s[i] + " ");
         aHeap.add(s[i]);
      }
      aHeap.display();
      return aHeap;
   } // creatMinHeap

Answer 1

你的add方法没有问题。问题出在您的 display 方法中。

您创建了一个堆，其中根节点位于数组中的索引 1 处。 display 方法的输出表明数组是：

[null, A, B, C, D, G, I, E, J, F, H, null, null, null, null, null, null, null, null, null]

如果我们忽略 0 元素（您选择不使用），则对应于此堆：

             A
        B         C
     D     G   I     E
    J F   H

这是有效的 min-heap。

我的建议是更改代码，使堆从索引 0 开始，而不是从索引 1 开始。这样可以避免很多混乱。您所要做的就是更改 parent 和 child 计算。索引 x 处的节点的 Parent 将位于 (x-1)/2。索引 x 处节点的左侧 child 是 (2*x)+1，右侧 child 是 (2*x)+2。当你添加一个节点时，你在递增 lastIndex.

之前将它添加到 a[lastIndex]

使用 Comparable 接口创建最小堆

Creating a minimum heap using the Comparable interface

java

heap

comparable