использование метода «extract» для итеративного удаления наименьшего элемента из минимальной кучи и копирования в назначенный arrayList в качестве метода получения отсортированного списка

Question

У меня есть программа, которая читает текстовый файл и создает несколько элементов узлов, которые можно использовать для встраивания в кучу MIN.

С чем я борюсь, так это то, что после того, как куча Min была правильно построена, я должен отсортировать элементы, используя метод extract, чтобы удалить наименьший элемент в корне и добавить его вотдельный ArrayList, предназначенный для хранения элементов в отсортированном порядке.

Конечно, мы должны извлекать по одному элементу за раз и добавлять его в наш новый массив, а затем удалять этот элемент из кучи оставшихся узлов, чтобы куча продолжала уменьшаться на один элемент, а отсортированная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

Мой класс кучи выглядит следующим образом:

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().