堆数据结构重新堆化方法

Question

我正在处理一个任务，需要从文本文件中读取前十个单词并存储到堆中。然后继续从文本文件中读取，如果这个词比堆的根节点小，则替换它并重新对整个堆进行排序。尽管我写的代码大多数情况下都能正常工作，但我还是遇到了一些问题。

• 有些单词虽然比堆顶小，但不会被交换
• 出现重复的单词

我应该得到一个包含以下单词的堆：abandoning abandons abased abash abashed abashes abasing abate abatement abbe

但我得到的单词是：abashes abashed abash abased abandons abandoning bewilderedly abandoning armful abandoning

---

以下是我目前的代码：

public static void readFile() {
    BufferedReader reader;
    String inputLine;
    int counter = 0;

    try {
        reader = new BufferedReader(new FileReader(".\\src\\dictionary.txt"));
        while((inputLine = reader.readLine()) != null) {
            if(counter < 10) {
                heap.insert(inputLine);
                counter++;
            }

            if(inputLine.compareTo(heap.find(0)) < 0) {
                heap.change(0, inputLine);
            }
        }
    } catch (IOException e) {
        System.out.println("Error: " + e);
    }
}

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

    Node newNode = new Node(value);
    heap[currentSize] = newNode;
    trickleUp(currentSize++);
    return true;
}

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

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

public void trickleDown(int index) {
    int largerChild;
    Node top = heap[index];

    while(index < currentSize / 2) {
        int leftChild = 2 * index + 1;
        int rightChild = index + 1;

        if(rightChild < currentSize && heap[leftChild].getData().compareTo(heap[rightChild].getData()) < 0) {
            largerChild = rightChild;
        } else {
            largerChild = leftChild;
        }

        if(top.getData().compareTo(heap[largerChild].getData()) > 0) {
            break;
        }

        heap[index] = heap[largerChild];
        index = largerChild;
    }
    heap[index] = top;
}

public boolean change(int index, String newValue) {
    if(index < 0 || index >= currentSize) { return false; }

    String oldValue = heap[index].getData();
    heap[index].setData(newValue);

    if(oldValue.compareTo(newValue) < 0) {
        trickleUp(index);
    } else {
        trickleDown(index);
    }
    return true;
}

- user2593573

---

你已经针对这个问题自己做了什么？ - bas

你是否在调试器下逐步运行它（假设你使用Eclipse或其他IDE）？ - PM 77-1

但您可以使用这10个单词进行测试。 - bas

trickleDown()方法的rightChild初始化非常可疑（至少缺少乘以2的操作）。 - Oleg Estekhin

正如@OlegEstekhin所说，int rightChild = index + 1; 应该改为 int rightChild = leftChild + 1;。 - CiaPan

Answer 1

如果使用这样的索引方式，您将无法得到二叉树：

    int leftChild = 2 * index + 1;
    int rightChild = index + 1;

我认为您的意思是这样写的：

我想你的意思应该是这样的：

    int leftChild = 2 * index + 1;
    int rightChild = 2 * index + 2;

所以树将会长成这样。

       0
     /   \
    1     2
   / \   / \
  3   4 5   6 
 / \
7   8 ... and so on

据我所知，堆可以包含重复元素，并且不支持重复删除。例如，以下是一个有效的数字堆。

      10
    /    \
   9      8
  / \    / \
 5   7  7   6

- Fefer_Ivan