Unsorted Insert List implementation of Priority Queue Rewrite implementation of

Question

Unsorted Insert List implementation of Priority Queue

Rewrite implementation of priority queue given in class PriorityQueueL.java with List defined as

    private int count;
    private List itemList;

(see List.java), so that it uses this unsorted, non-recursive metod insert (it is mandatory thet you use this code with no modifications)

    public void insert(int newItem)
    {
        cnt.incr();
        List N = new List();
        N.head=newItem;
        N.tail=itemList;
        itemList=N;
        count++;
    }
  
and appropriately modified remove() method that removes the largest element from the priority queue passed to it as the implicit argument.

You may need to implement a method that finds the largest element in a List defined above, first.

After the above modifications, your class PriorityQueueL.java must work as needed when invoked by the sorting method included in class PriorityQueueTestL.java.

In particular, both the sorting and the values of T(n) must be correct.

You are supposed to add to your program any other classes (for instance, cnt.java) that might be necessary; you may re-use them from previous projects if appropriate.

PriorityQueueL.java

--- computed results by your program for arrays (to be sorted) of sizes from 1 to 20, each of which including increasigly sorted, decreasingly sorted, and pseudo-random array, just like the code in classPriorityQueueTestL.java is designed to do.

public class PriorityQueueTestL {
  
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int[] Array;
int N;
for (N = 1; N<=100; N++)
{
Array = new int[N];
for (int i = 0; i < N; i++)
Array[i] = (int)(Math.sqrt(97)*(13*i + 1)*(19*i + 2)+i - 17)%1000;
for (int i = 0; i < N; i++)
Array[i] = -i;
  
// for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
// System.out.println();
cnt.clr(); //counts moves of keys while sorting
Bcnt.clrAll(); //counts comparisons of keys while sorting
PriorityQueueSort(Array);
for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
System.out.println();
// Tcomp(N) is the sorting "time" measured by the number of comparisons
// of keys
System.out.print("Tcomp(" + N +")");
Bcnt.out(" = ");
System.out.print(" " + ( N*(N-1)/2) + " = N*(N-1)/2" + " ");
// Tcall(N) is the sorting "time" measured by the number of calls
System.out.print(" Tcall(" + N +")");
cnt.out(" = ");
System.out.println(" " + (2*N + N*(N-1)/2) + " = 2*N + N*(N-1)/2");
  
}
}
public static void PriorityQueueSort(int[] A)
{
int n = A.length;
PriorityQueueL PQ = new PriorityQueueL();
for (int i = 0; i < n; i++) PQ.insert(A[i]);
// for (int i = n-1; i >= 0; i--) PQ.insert(A[i]);
// System.out.println("A Size of PQ is " + PQ.Length());
for (int i = n-1; i >= 0; i--) A[i]=PQ.remove();
// for (int i = 0; i < n; i++) A[i]=PQ.remove();
// System.out.println("B Size of PQ is " + PQ.Length());
  
}

}

Explanation / Answer

using System; using System.Collections; using System.Collections.Generic; namespace HeapADT { public class Heap : ICollection, IEnumerable where T : IComparable { #region Private Members private readonly List m_Items; private readonly IComparer m_Comparer; #endregion #region Constructors public Heap() : this(0) {} public Heap( int capacity ) : this( capacity, null ) {} public Heap( IEnumerable items ) : this( items, null ) {} public Heap( int capacity, IComparer comparer ) { m_Items = new List(capacity); m_Comparer = comparer ?? Comparer.Default; } public Heap( IEnumerable items, IComparer comparer ) { m_Items = new List(items); m_Comparer = comparer ?? Comparer.Default; BuildHeap(); } #endregion #region Operations public void Add( T item ) { m_Items.Add( item ); var itemIndex = Count - 1; while( itemIndex > 0 ) { var parentIndex = ParentIndex(itemIndex); // are we a heap? If yes, then we're done... if( m_Comparer.Compare( this[parentIndex], this[itemIndex] ) < 0 ) return; // otherwise, sift the item up the heap by swapping with parent Swap( itemIndex, parentIndex ); itemIndex = parentIndex; } } public T RemoveRoot() { if( Count == 0 ) throw new InvalidOperationException("Cannot remove the root of an empty heap."); var rootItem = this[0]; ReplaceRoot(RemoveLast()); return rootItem; } public T RemoveLast() { if( Count == 0 ) throw new InvalidOperationException("Cannot remove the tail from an empty heap."); var leafItem = this[Count - 1]; m_Items.RemoveAt( Count-1 ); return leafItem; } public void ReplaceRoot( T newRoot ) { if (Count == 0) return; // cannot replace a nonexistent root m_Items[0] = newRoot; Heapify(0); } public T this[int index] { get { return m_Items[index]; } private set { m_Items[index] = value; } } #endregion #region Private Members private void Heapify( int parentIndex ) { var leastIndex = parentIndex; var leftIndex = LeftIndex(parentIndex); var rightIndex = RightIndex(parentIndex); // do we have a right child? if (rightIndex

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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