使用'extract'方法迭代从最小堆中取出最小元素并复制到指定的arrayList作为获得排序列表的方法

Question

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

我遇到的问题是，在正确构建最小堆之后，我应该使用 'extract' 方法对元素进行排序，以删除根部的最小元素并将其添加到一个单独的 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());
        }

我不断得到的输出如下：

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

我的堆class如下：

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

这个循环将运行一遍又一遍，直到你的堆中什么都没有，然后该函数将 return 最后一个节点 min 设置为（应该是原始堆中最大的元素，如果 Heapify 正确实现）。随后的调用将看到 heapSize == 0，完全跳过循环，并立即将 return min 设置为 A.get(0)，它仍然是原始堆。每次调用heap_Extract().

使用'extract'方法迭代从最小堆中取出最小元素并复制到指定的arrayList作为获得排序列表的方法

using 'extract' method to iteratively remove smallest element from min heap and copy to designated arrayList as a method of obtaining a sorted list

java

heap

extract

heapsort