java使用“extract”方法从最小堆中迭代删除最小元素，并复制到指定的arrayList，作为获得排序列表的方法

Question

我有一个程序，可以读取文本文件，并创建一些节点元素，这些元素可以用来构建一个最小堆

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

当然，我们应该一次提取一个元素，并将其添加到新的arraylist中，然后从剩余节点的堆中删除该元素，这样堆将不断减少一个元素，排序的arraylist将不断增加一个元素，直到堆中没有剩余的元素

我认为问题在于，在提取min heap的根元素之后，根元素本身并没有被擦除，它似乎保留在堆中，即使我的extract方法应该覆盖已删除的根元素，方法是用堆中的最后一项替换它，然后减小堆大小并重新应用“heapify”方法来恢复heap属性

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

        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());
        }

我得到的结果如下：

the 0th remaining element in ordered node list is: 55
the 1th item added to SORTED node list is: F 55

the 0th remaining element in ordered node list is: 55
the 2th item added to SORTED node list is: F 55

the 0th remaining element in ordered node list is: 55
the 3th item added to SORTED node list is: F 55

the 0th remaining element in ordered node list is: 55
the 4th item added to SORTED node list is: F 55

the 0th remaining element in ordered node list is: 55
the 5th item added to SORTED node list is: F 55

the 0th remaining element in ordered node list is: 55
sorted node list after extract method*****************

 F
sorted node list after extract method*****************

 F
sorted node list after extract method*****************

 F
sorted node list after extract method*****************

 F
sorted node list after extract method*****************

 F
sorted node list after extract method*****************

 F

我的Heap类如下所示：

import java.util.*;

public class Heap 
{
int heapSize;
ArrayList unordered_nodeList;
ArrayList ordered_nodeList;
Graph gr;

nodes
public Heap(ArrayList<Node> A, Graph g)
{
    unordered_nodeList = g.getNodeList();
    heapSize = unordered_nodeList.size();
    ordered_nodeList = A;
    gr = g;
}

public ArrayList getUnordered_nodeList() {
    return unordered_nodeList;
}

public void setUnordered_nodeList(ArrayList unordered_nodeList) {
    this.unordered_nodeList = unordered_nodeList;
}

public ArrayList getOrdered_nodeList() {
    return ordered_nodeList;
}

public void setOrdered_nodeList(ArrayList ordered_nodeList) {
    this.ordered_nodeList = ordered_nodeList;
}

public int getHeapSize() {
    return heapSize;
}

public void setHeapSize(int heapSize) {
    this.heapSize = heapSize;
}

//heap methods

public int Parent(ArrayList<Node> A, int i)
{
    //if (i == 1)
        //return (Integer)null;

    if (i%2 != 0)
        return i/2;

    else 
        return (i-1)/2;
}

public int Left(ArrayList<Node> A, int i)
{
    if (2*i < A.size()-1)
        return (2*i)+1;
    else
        return i;
        //return (Integer)null;
}

public int Right(ArrayList<Node> A, int i)
{
    if ((2*i)+1 < A.size()-1)
        return 2*i+2;
    else
        return i;
        //return (Integer)null;
}

public void Heapify(ArrayList<Node> A, int i)
{
    Node smallest;
    Node temp;
    int index;

    int l = Left(A,i);
    int r = Right(A,i);

    if (l <= heapSize-1 && Integer.parseInt(A.get(l).getVal()) < Integer.parseInt(A.get(i).getVal()))
    {   
        //left child is smaller
        smallest = A.get(l);
        index = l;
    }   
    else
    {   
        //parent node is smaller
        smallest = A.get(i);
        index = i;
    }   

    if (r <= heapSize-2 && Integer.parseInt(A.get(r).getVal()) < Integer.parseInt(smallest.getVal()))
    {   
        //right child is smaller
        smallest = A.get(r);
        index = r;
    }

    if (index != i)
    {   
        //if the smallest element is not the parent node
        //swap the smallest child with the parent  
        temp = A.get(i);
        A.set(i, A.get(index));
        A.set(index, temp);

        //recursively call heapify method to check next parent/child relationship
        Heapify(A, index);

        //System.out.println(this.heapClass_toString(ordered_nodeList));
    }
    //System.out.println("\n**********************" + "\nHeapify line 123" + this.heapClass_toString(ordered_nodeList));
}   

//method to construct min heap from unordered arraylist of nodes
public void Build_min_Heap(ArrayList<Node> A)
{
    int i;
    int heapSize = A.size();

    for (i = (heapSize/2); i>=0; i--)
    {   
        //System.out.println(gr.toString2() +"\n");
        //System.out.println("build heap ********** line 138" +this.heapClass_toString(ordered_nodeList));
        Heapify(A, i);
        //System.out.print(gr.toString2()+"\n");
    }       
}

//method to sort in descending order, a min heap
public void heap_Sort(ArrayList<Node> A)
{
Node temp;


    //Build_min_Heap(A);
while (A.size() > 0)
{   
    ///System.out.println("\n******************************\n heap_sort line 180" +this.heapClass_toString(ordered_nodeList));

    //for (int i = 0; i <= A.size()-1; i++)
    for(int i = A.size()-1; i >= 1; i--)
    {
        //exchange a[0] with a[i]
        temp = A.get(0);
        A.set(0, A.get(i));
        A.set(i, temp);

        //System.out.println(this.heapClass_toString(ordered_nodeList));

        //decrement heapSize
        heapSize--;

        //recursive heapify call
        Heapify(A, 0);

        System.out.println("\n******************************\n heap_sort line 203" +this.heapClass_toString(ordered_nodeList));
    }   
    System.out.println("\n******************************\n heap_sort line 206" +this.heapClass_toString(ordered_nodeList)); 
    Heapify(A, A.size()-1);
}
}


public Node heap_Extract(ArrayList<Node> A)
{

    //Node min = null;

    //if (heapSize>0)   
    //while (A.get(0) != null && heapSize > 0)  
    Node min = A.get(0);

    //min = A.get(0);
    while (heapSize>0)
    {   
        min = A.get(0);

        A.set(0, A.get(heapSize-1));

        //decrement heapSize
        heapSize--;
        Heapify(A, 0);  
    }   
    return min;
}
    //return min;

public String heapClass_toString(ArrayList A)
{
    String s = "Graph g.\n";
    if (A.size() > 0 ) 
    {
        for (int k = 0; k < A.size(); k++ )
        {
            //output string to print each node's mnemonic 
            String t = this.getOrdered_nodeList().get(k).toString();

            s = s.concat(t);        
        }   
    }
    return s;
} 

}

Answer 1

一个问题是heap_Extract()方法中的以下循环：

while (heapSize>0)
{   
    min = A.get(0);

    A.set(0, A.get(heapSize-1));

    //decrement heapSize
    heapSize ;
    Heapify(A, 0);  
} 

这个循环将一次又一次地运行，直到堆中没有任何内容，然后该函数将返回设置为的最后一个节点min（如果Heapify正确实现，它应该是原始堆中最大的元素）。随后的调用将看到heapSize == 0，完全跳过循环，并立即返回min，它将被设置为A.get(0)，它仍然是原始堆中最大的元素。对于heap_Extract()的每次调用，应该确保此循环体中的代码最多只运行一次（即，它不应该在循环中，但可能应该由其他一些条件分支语句保护）