java - 字符串堆未正确插入

Question

我一直在做我的作业，即创建一堆字符串，并对其执行各种功能。我现在正在测试我的代码，看看它是否正确插入，但事实并非如此。我正在测试这些词: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;
}

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

Answer 1

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

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

来自介绍性段落(添加了重点):

Either the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node (this kind of heap is called max heap) or the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node (min heap).

从第二段(添加强调):

there is no implied ordering between siblings or cousins and no implied sequence for an in-order traversal (as there would be in, e.g., a binary search tree). The heap relation mentioned above applies only between nodes and their immediate parents.

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