1

我一直在做我的任务，即创建一堆字符串，并在其上执行各种功能。我现在正在测试我的代码以查看它是否正确插入，但事实并非如此。我正在测试这些词：Golf, Bravo, Hotel, Alpha, Delta, Echo, Charlie, Foxtrot它会按字母顺序插入它们但是当我打印我的堆时我最终得到：

                                Alpha
             Bravo                              Charlie
   Foxtrot              Delta              Hotel              Echo
Golf

这是我编写的代码：

public boolean insert(String key) {
    if(currentSize == maxSize) {
        return false;
    }

    Node newNode = new Node(key);
    heapArray[currentSize] = newNode;
    trickleUp(currentSize++);
    return true;
}

public void trickleUp(int index) {
    int parent = (index - 1) / 2;
    Node bottom = heapArray[index];

    while(index > 0 && heapArray[parent].getKey().compareTo(bottom.getKey()) > 0) {
        heapArray[index] = heapArray[parent];
        index = parent;
        parent = (parent - 1) / 2;
    }
    heapArray[index] = bottom;
}

编辑：在快速搜索并找到堆的另一个源代码并对其进行测试后，我得到了相同的输出。有没有理由不按字母顺序添加？

4

1 回答 1

0

您在打印输出中显示的行为对于最小堆是正确的，请参阅：

http://en.wikipedia.org/wiki/Heap_(data_structure)

从介绍性段落（强调添加）：

要么父节点的key总是大于等于子节点的key，最高的key在根节点（这种堆称为max heap），要么父节点的key小于等于子节点的key子节点和最低键位于根节点（最小堆）中。

从第二段（强调添加）：

兄弟姐妹或堂兄弟之间没有隐含的顺序，也没有中序遍历的隐含序列（例如，二叉搜索树中会有）。上面提到的堆关系只适用于节点和它们的直接父节点之间。

您的堆显示正确排序，因为每个节点只有大于它的子节点，按字母顺序排列。

于 2013-07-29T00:20:12.033 回答