Create a java program using heapsort for sorting a list of inputs stored in entr

ID: 3681066 • Letter: C

Question

Create a java program using heapsort for sorting a list of inputs stored in entry.txt file. Print the output of preordertraversal of the heap you created and the sorted list.

The Hint:

Use HeapPriorityQueue code to create the heap we needed. Either use AbstractTree code to implement preorder traversal or use this algorithm yourself.

The Input:

The common input for this program which is in the entry.txt is as following:

<3, A> <8, Z> <12, B> <9, M> <17, T> <31, U> <13, D> <24, E> <9, L> <7, B> <1, N> <5, G>

The Output:

For the given input, the corresponding output is:

Preorder:

<1, N> <3, A> <9, M> <24, E> <9, L> <7, B> <17, T> <8, Z> <5, G> <12, B> <31, U> <13, D>

Sorted List:

<1, N> <3, A> <5, G> <7, B> <8, Z> <9, L> <9, M> <12, B> <13, D> <17, T> <24, E> <31, U>

Please provide a working code for the above scenario using heapPriorityQueue Code, Thanks

Explanation / Answer

Note: code is implemented as user request. with given time, i could nt make program to read input from file. hence manually inserted values to the priority queue.

Code:

import java.util.*;
import java.io.*;
import java.lang.*;
class item
{
int k;
char v;
public item(int k1,char v1)
{
k=k1;
v=v1;
}
public item(item i)
{
this(i.k,i.v);
}
public String toString()
{
return "<"+k+","+v+">";
}
}

class HeapPriorityQueue
{
   private item[] heapElement;
   private int heapSize;


   public HeapPriorityQueue() {
   heapElement = new item[10];
   heapSize = 0;
   }


   public void addHeapElement(int k,char v)
   {
       item newItem=new item(k,v);

   if (heapSize + 1 >= heapElement.length)
       {
       heapElement = Arrays.copyOf(heapElement, heapElement.length * 2);
   }


   heapElement[heapSize + 1] = newItem;


   int ind1 = heapSize + 1;
   boolean found = false;
   while (!found && hasparentItem(ind1))
       {
       int parentItm = parentItem(ind1);
       if (heapElement[parentItm].k>heapElement[ind1].k)
           {
       swapHeapElement(heapElement,ind1, parentItem(ind1) );
       ind1 = parentItem(ind1);
       }
           else
           {
       found = true;
       }
   }

   heapSize++;
   }


   public boolean isEmpty()
   {
   return heapSize == 0;
   }







   public int heapSize()
   {
   return heapSize;
   }


   public String toString()
   {
   String r1 ="";
   if (!isEmpty())
       {
       r1 += heapElement[1].toString();
       for (int k1 = 2; k1 <= heapSize; k1++)
           {
       r1 += ", " + heapElement[k1].toString();
       }
   }
   return r1;
   }



   private int parentItem(int ind1)
   {
   return ind1 / 2;
   }


   private int leftChildItem(int ind1)
   {
   return ind1 * 2;
   }


    private int rightChildItem(int ind1)
   {
   return ind1 * 2 + 1;
   }


   private boolean hasparentItem(int ind1)
   {
   return ind1 > 1;
   }


   private boolean hasleftChildItem(int ind1)
   {
   return leftChildItem(ind1) <= heapSize;
   }


   private boolean hasrightChildItem(int ind1)
   {
   return rightChildItem(ind1) <= heapSize;
   }


   private void swapHeapElement(item[] a, int ind1, int ind2)
   {
   item temp = a[ind1];
   a[ind1] = a[ind2];
   a[ind2] = temp;
   }
   private void performHeapify( item[] heapElement, int s, int t )
   {

       while (true) {
           int c1 = 2*t+1;
           int c2 = 2*t+2;

           if (c1 >= s)
               break;
           int bChild;
           if (c2 >= s || heapElement[c1].k >= heapElement[c2].k)
               bChild = c1;
           else
               bChild = c2;
           if (heapElement[bChild].k <= heapElement[t].k)
               break;
           item temp1 = heapElement[t];
           heapElement[t] = heapElement[bChild];
           heapElement[bChild] = temp1;
           t = bChild;
       }
   }
   public void heapSort( )
   {
       int n=heapSize();
       for (int t = n/2; t >= 0; t--) {
           performHeapify(heapElement,n,t);
       }
       for (int t = n-1; t > 0; t--) {

           item temp1 = heapElement[t];
           heapElement[t] = heapElement[0];
           heapElement[0] = temp1;
           performHeapify(heapElement,t,0);
       }
   }
}
public class HelloWorld{

public static void main(String []args){
HeapPriorityQueue h=new HeapPriorityQueue();

h.addHeapElement(3,'A');
h.addHeapElement(8,'Z');
h.addHeapElement(12,'B');
h.addHeapElement(9,'M');
h.addHeapElement(17,'T');
h.addHeapElement(31,'U');
h.addHeapElement(13,'D');
h.addHeapElement(24,'E');
h.addHeapElement(9,'L');
h.addHeapElement(7,'B');
       h.addHeapElement(1,'N');
h.addHeapElement(5,'G');

System.out.println(h);
h.heapSort();
System.out.println(h);
}
}

Navigate

Create a java program to produce random sentences using arrays. There should be

Create a java program using the following requirements The numbers below are fro

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Create a java program using heapsort for sorting a list of inputs stored in entr

Question

Explanation / Answer

Related Questions

Navigate