使用 'extract' 方法从最小堆中迭代删除最小元素并复制到指定的

Question

我有一个程序，它读入一个文本文件并创建许多可用于构建 MIN 堆的节点元素。

我正在努力解决的是，在正确构建最小堆后，我应该通过使用“提取”方法对元素进行排序，以删除根处的最小元素并将其添加到旨在包含的单独 ArrayList 中排序后的元素。

当然，我们应该一次提取一个元素并将其添加到我们的新数组列表中，然后从剩余节点的堆中删除该元素，以便堆不断减少一个元素，而排序后的数组列表则不断增加一个元素直到堆中没有剩余元素。

我相信问题是在提取最小堆的根元素后，根元素本身没有被删除，它似乎仍然留在堆中，即使我的提取方法应该通过将其替换为覆盖已删除的根元素堆中的最后一项，然后递减堆大小并重新应用“heapify”方法来恢复堆属性。

我的代码相当简单，主要方法很长，但重要的部分如下：

        g = new Graph();

        readGraphInfo( g );

        DelivB dB = new DelivB(inputFile, g);

        int numElements = g.getNodeList().size();

        ArrayList<Node> ordered_nodeList = new ArrayList<Node>(15);

        ArrayList<Node> sorted_nodeList = new ArrayList<Node>(15);

        h = new Heap(ordered_nodeList, g);

        for (int i = 0; i < numElements; i++)

        {

            ordered_nodeList.add(i, g.getNodeList().get(i));

            h.Build_min_Heap(ordered_nodeList);

            System.out.println("Heap: \n");

            System.out.println("\n**********************" + "\nProg 340 line 147" +h.heapClass_toString(ordered_nodeList)); 

            //System.out.println("the " + i + "th item added at index " + i + " is: " + ordered_nodeList.get(i).getAbbrev());

        }

        for (int j = 0; j < numElements; j++)

        {

            sorted_nodeList.add(j, h.heap_Extract(ordered_nodeList));

            System.out.println("the "+j+"th item added to SORTED node list is: "+sorted_nodeList.get(j).getAbbrev()+ " "+ sorted_nodeList.get(j).getVal());

            //h.heap_Sort(ordered_nodeList);

            System.out.println("\nthe 0th remaining element in ordered node list is: " + ordered_nodeList.get(0).getVal());

            h.Build_min_Heap(ordered_nodeList);

        }

        for (Node n : sorted_nodeList)

        {

            System.out.println("sorted node list after extract method*****************\n");

            System.out.println(n.toString());

        }

Answer 1

一个问题是您的heap_Extract()方法中的以下循环：while (heapSize>0){&nbsp; &nbsp;&nbsp; &nbsp; min = A.get(0);&nbsp; &nbsp; A.set(0, A.get(heapSize-1));&nbsp; &nbsp; //decrement heapSize&nbsp; &nbsp; heapSize--;&nbsp; &nbsp; Heapify(A, 0);&nbsp;&nbsp;}&nbsp;这个循环会一遍又一遍地运行，直到你的堆里没有任何东西，然后函数将返回最后一个节点min设置为（如果Heapify正确实现，它应该是原始堆中的最大元素）。随后的调用将看到 ，heapSize == 0完全跳过循环，并立即返回min，它将被设置为A.get(0)，这仍然是原始堆中的最大元素。您应该确保此循环体中的代码对于每次调用heap_Extract().