I have a program that reads in a text file and creates a number of nodes elements that can be used to build into a MIN heap.
What I'm struggling with is, after the Min heap has been correctly built, I'm supposed to sort the elements by using an 'extract' method to remove the smallest element at the root and adding it to a separate ArrayList intended to contain the elements in sorted order.
Of course we are supposed to extract one element at a time and add it to our new arraylist and then, remove that element from the heap of remaining nodes, so that the heap keeps decreasing by one element and the sorted arraylist keeps increasing by one element until there are no remaining elements in the heap.
I believe the problem is that after extracting the root element of the min heap, the root element itself isn't erased, it seems to remain in the heap even though my extract method is supposed to overwrite the removed root element by replacing it with the last item in the heap and then decrementing the heap size and re-applying the 'heapify' method to restore the heap property.
My code is fairly simple, the main method is long but the significant part is as follows:
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 output I keep getting is as follows:
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
My Heap class is as follows:
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;
}
}
One issue is the following loop in your heap_Extract() method:
while (heapSize>0)
{
min = A.get(0);
A.set(0, A.get(heapSize-1));
//decrement heapSize
heapSize--;
Heapify(A, 0);
}
This loop will run over and over again until your heap has nothing in it, and then the function will return the last node min was set to (which should be the largest element in the original heap, if Heapify is implemented correctly). Subsequent calls will see that heapSize == 0, skip the loop entirely, and immediately and return min, which will be set to A.get(0), which will still be the largest element in the original Heap. You should ensure that the code in the body of this loop only runs at most one time (i.e. it shouldn't be in a loop, but perhaps should be guarded by some other conditional branch statement) for each call of heap_Extract().