为什么 bubbleDown 方法没有按预期工作（堆排序）？

Question

这是一项到期的作业，我在 C++ 和 Java 中都尝试过，但在这两个版本中，bubbleDown 方法都没有按预期工作，尽管我相信逻辑表明它应该.两个版本我都已经交了，不过Java版本是最新的，所以我会post放在这里

这是 Java 版本：

import java.io.*;
import java.util.Scanner;

public class HeapSort {
    static int[] heap;
    Integer[] sorted;
    String in, out;
    int fullLength = 0;

    public HeapSort(String inf, String outf) throws FileNotFoundException {
        in = inf;
        out = outf;

        Scanner scan = new Scanner(new File(in));
        while (scan.hasNextInt()) {
            fullLength++;
            scan.nextInt();
        }

        sorted = new Integer[fullLength];
        heap = new int[fullLength+1];
        heap[0] = 0;

        scan.close();
    }

    public boolean isFull() {
        return heap[0] == fullLength;
    }

    public boolean isEmpty() {
        return heap[0] == 0;
    }

    public void buildHeap() throws IOException {
        Scanner scan = new Scanner(new File(in));
        while (scan.hasNextInt())
            insertOneDataItem(scan.nextInt());

        scan.close();
    }

    public void deleteHeap() throws IOException {
        while (!isEmpty()) {
            deleteRoot();
            printHeap();
        }
    }

    public void deleteRoot() throws IOException {
        if (isEmpty())
            return;

        FileWriter f = new FileWriter(out, true);
        f.write("Deleting " + heap[1] + "\n");
        f.close();
        int i;
        for(i = 0; sorted[i] != null; i++);
        sorted[i] = heap[1];
        heap[1] = heap[heap[0]--];
        bubbleDown();
    }


    public void insertOneDataItem(int num) throws IOException {
        if (isFull()) {
            p("Heap is full");
            return;
        }

        heap[++heap[0]] = num;
        bubbleUp();
        printHeap();
    }

    public void printHeap() throws IOException {
        FileWriter f = new FileWriter(out, true);
        f.write("Current Heap:\t");
        for (int i = 1; i <= heap[0]; i++) {
            if (i > 10) break;
            f.write(heap[i] + " ");
        }
        f.write("\n");
        f.close();
    }

    public void printSorted() throws IOException {
        FileWriter f = new FileWriter(out, true);
        f.write("Current Sorted:\t");
        for (int i = 1; i <= sorted.length; i++) {
            if (i > 10) break;
            f.write(sorted[i] + " ");
        }
        f.write("\n");
        f.close();
    }

    public void bubbleUp() {
        int h = heap[0];
        while (h >= 2 && heap[h] < heap[h/2]) {
            int x = heap[h];
            heap[h] = heap[h/2];
            heap[h/2] = x;
            h = h/2;
        }
    }

    public void bubbleDown() {
        int k = 1;
        // make sure we have at least a left child
        // before continuing on
        while (2*k <= heap.length) {
            int left = 2*k;
            int right = 2*k+1;
            if (heap[k] >= heap[left]) {
                int x = heap[k];
                heap[k] = heap[left];
                heap[left] = x;
                k = left;
                continue;
            }
            if (right <= heap.length &&
                heap[k] >= heap[right]) {
                int x = heap[k];
                heap[k] = heap[right];
                heap[right] = x;
                k = right;
            } else {
                return;
            }
        }
    }

    public void begin() throws IOException {
        buildHeap();
        deleteHeap();
        printSorted();
    }

    public static void main(String[] args) throws IOException {
        if (args.length < 2) {
            p("Please start with: program file1.txt file2.txt");
            System.exit(1);
        }

        // empty the output file
        (new FileOutputStream(args[1])).close();

        (new HeapSort(args[0], args[1])).begin();

    }

    public static void p(String s) {
        System.out.println(s);
    }
}

输入文件 (args[0]) 在文件中只有整数，有些在同一行，有些在不同行。 args[1] 是输出文件名。

当程序通过 bubbleDown 时，它开始按预期工作，但随后它跳过了一些数字，最后我最终会看到一个本应位于顶部的数字。有人可以向我解释一下我在这个函数中做错了什么吗？

Answer 1

出于多种原因，您的代码看起来很可疑。 1——你将实际的数据结构实现与读取一个没有意义的文件混合在一起。很难遵循。那么这块就不能对了：

sorted[i] = heap[1];
heap[1] = heap[heap[0]--];

第一行表明堆数组包含实际数据元素。但是第二行是将堆内容视为某种索引吗？ heap[0]-- 会递减存储在堆数组位置 0 的值，但首先它会使用它来将 heap[heap[0]] 的内容移动到 heap[1]？什么？您是否使用 heap[0] 作为特殊的东西来存储数组中最后一个元素的索引？我建议您首先像这样重写代码 w/o hack，它应该更容易理解和修复。实际上，您的堆应该从元素 0 开始，您的左节点将在 2k+1，右节点将在 2k+2。

现在这闻起来好像是错误的：

right <= heap.length

您应该与那个可怕的堆[0] 进行比较，因为当您从中移除东西时heap.length 不会缩小。

for (int i = 1; i <= sorted.length; i++) {

应该是

for (int i = 0; i < sorted.length; i++) {

最后的 main 错误在 bubbleDown 方法中。向下冒泡时，您需要将向下移动的节点与其 children 的 smaller 交换。所以就是7在冒泡，它的左child是6，右child是4，你需要交换7和4，否则你得到无效的树

   6
 /   \
7     4

所以代码应该是

if (heap[k] >= heap[left] && heap[left] < heap[right]) {

不客气。你的教授欠我午餐，因为他为他做了他的工作。

为什么 bubbleDown 方法没有按预期工作（堆排序）？

Why isn't the bubbleDown method working as intended (Heap Sort)?

java

heapsort