Hi all, I\'m trying to modify this Java code of a Heap Implementation of a Prior

Question

Hi all,

I'm trying to modify this Java code of a Heap Implementation of a Priority Queue and turn it into a 3-Heap Implementation of a Priority Queue. But, I don't know where to begin. I want to sort the queue in increasing, decreasing, and random order. All I know is that a 3-Heap is similar to a Heap, but with two separate trees and the parent node can have at most 3 children. From my algorithm, I'm trying to store the roots in indices 1 & 2, have the children of the first root stored in indices 3, 4, & 5, and have the children of the 2nd root stored in indices 6, 7,and 8. I'm thinking about calling the 1st root i, its left child 3i, middle child 3i + 1, & right child 3i + 2. For the 2nd root, i'm thinking about calling it 2i, its left child 2i + 4, middle child 2i + 5, and right child 2i + 6. But, I don't even know if that's right.

Can anyone please help me modify my code to 3-Heap? Or just give me some tips on how to turn a 2-Heap PQ into a 3-Heap PQ?

Any help is appreciated. Thanks!

Here is my PriorityQueue class and my driver class called PriorityQueueTest.

public class PriorityQueue {
  
//Uses heap as implementation
  

private int count; //actual number of elements
private int capacity; //the size of the array - 1 (itemArray[0] never used)
private int capacityIncrement;
private int[] itemArray;
  
/** Creates a new instance of PriorityQueue */
public PriorityQueue() {
count=0;
capacity=10;
capacityIncrement=2;
itemArray=new int[capacity + 1]; //itemArray[0] never used
}
  
public void insert(int newItem)
{
if(count==capacity) //no more space, "resize" the array up
{
capacity*=capacityIncrement;
int[] tempArray = new int[capacity + 1]; //because itemArray[0] is not used
for (int i = 1; i <= count; i++)
{
tempArray[i] = itemArray[i];
cnt2.incr();
}
itemArray = tempArray;

}
//try insert at the end
count++; //1st element sits at index 1, 2nd element at index 2, etc,...
//the newly inserted element may be too large to be a leaf
int i = count; //initial "logical" position of newItem
//we keep it in itemArray[0] to save time on swapping
while ((i > 1) && (cnt3.incr() & (newItem > itemArray[i/2])))
{
itemArray[i] = itemArray[i/2]; //demote the parent
cnt.incr();
i = i/2; //promote the new one i /= 2;
}
//here i is the index for the newly inserted element
itemArray[i] = newItem;
cnt.incr();
}
  
public int remove()
{
if (count==0) return -9999;
//here count != 0
int maxItem = itemArray[1]; //the root
int demotee = count;
count--;
int i = 1;
boolean demoted = true;
while ((2*i <= count) && demoted)
{
int j = 2*i; // first child
if ((j < count) && (cnt3.incr() & (itemArray[j] < itemArray[j + 1]))) j++;
if (cnt3.incr() & (itemArray[j] > itemArray[demotee])) //demote patch
{
itemArray[i] = itemArray[j]; //promote its larger child
cnt.incr();
i = j; //demote patch's index

}
else
{
demoted = false;
}
}
//i is the place for the patch
itemArray[i] = itemArray[demotee];
cnt.incr();
itemArray[demotee] = 0; // for demonstration purpose only

if ((count < capacity / capacityIncrement) && (10 <= capacity / capacityIncrement)) //space wasted, "resize" the array down
{
capacity/=capacityIncrement;
int[] tempArray = new int[capacity+1]; //because itemArray[0] is not used
for (i = 1; i <= count; i++)
{
tempArray[i] = itemArray[i];
cnt2.incr();
}
itemArray = tempArray;
}
return maxItem;
}

public int size()
{
return count;
}
  
public boolean isEmpty()
{
return count==0;
}

public int Length()
{
return itemArray.length;
}
  
public void dump()
{
System.out.print("Dump heap: ");
for (int i = 1; i <= count; i++) System.out.print(itemArray[i] + " ");
System.out.println();
}
}

public class PriorityQueueTest {

// /** Creates a new instance of PriorityQueueTest */
// public PriorityQueueTest() {
// }
  
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int[] Array;
int Lim = 20;
int N;
for (N = 1; N<=Lim; 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)%(100*Lim);
// for (int i = 0; i < N; i++)
// Array[i] = -i;
System.out.println("*** N = " + N + " ***");
System.out.print("Input: ");
for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
System.out.println();
cnt.clr(); //counts copying of keys while sorting
cnt2.clr(); //counts copying of keys while resizing
cnt3.clr(); //counts comparisons of keys
PriorityQueueSort(Array);
System.out.print("Sorted: ");
for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
System.out.println();
System.out.print("C(" + N +")");
cnt3.out(" = ");
int Flgn = (int)(Math.floor(Math.log(N)/Math.log(2)));
int Flgn1 = (int)(Math.max(0,Math.floor(Math.log(N-1)/Math.log(2))));
int E2Flgn = 1;
for (int i = 0; i < Flgn; i++)
E2Flgn *= 2;
System.out.println(" Worst case comps = " + ((3*N+1)*Flgn - 3*E2Flgn*2 -Flgn1 + 6) +
" = (3*N+1)*Flgn - 3*E2Flgn*2 - Flgn1 + 6");
if (N < 3) System.out.println("A lower bound on best case comps = " + (N - 1) + " = N - 1");
else System.out.println("A lower bound on best case comps = " + (3 * (N - 2)) + " = 3*(N - 2)");
System.out.print("M(" + N +")");
cnt.out(" = ");
System.out.println(" Worst case moves while sorting = " + ((2*N+1)*Flgn + 2*N - 2*E2Flgn*2 + 4) +
" = (2*N+1)*Flgn + 2*N - 2*E2Flgn*2 + 4");
System.out.println("A lower bound on best case moves while sorting = " + (2*N) + " = 2*N");
System.out.print("R(" + N +")");
cnt2.out(" = ");
int Clgn10 = (int)(Math.max(0,Math.ceil(Math.log(N/10.0)/Math.log(2))));
int E2Clgn10 = 1;
for (int i = 0; i < Clgn10; i++)
E2Clgn10 *= 2;
System.out.println(" = " + (int)(20*E2Clgn10 - Clgn10 - 20) + " = 20*E2Clgn10 - Clgn10 - 20");
System.out.println();
}
}
public static void PriorityQueueSort(int[] A)
{
int n = A.length;
PriorityQueue PQ = new PriorityQueue();
for (int i = 0; i < n; i++) PQ.insert(A[i]);
System.out.println("A: Length of itemArray in PQ is " + PQ.Length());
System.out.println("A: Size of PQ is " + PQ.size());
PQ.dump();
for (int i = 0; i < n; i++) A[i]=PQ.remove();
System.out.println("B: Length of itemArray in PQ is " + PQ.Length());
System.out.println("B: Size of PQ is " + PQ.size());
}
}
  

Explanation / Answer

import java.util.ArrayList; public class HeapMinPriorityQueue implements MinPriorityQueue { private ArrayList heap; /** * Constructor */ public HeapMinPriorityQueue() { heap = new ArrayList(); } /** * Return the element with the minimum key, and remove it from the queue. * @return the element with the minimum key, or null if queue empty. */ public E extractMin() { if (heap.size() 0 && heap.get(loc).compareTo(heap.get(parent(loc))) < 0) { swap(heap, loc, parent(loc)); loc = parent(loc); } } /** * Is the priority queue empty? * @return true if the queue is empty, false if not empty. */ public boolean isEmpty() { return heap.size() == 0; } /** * Return the element with the minimum key, without removing it from the queue. * @return the element with the minimum key, or null if queue empty. */ public E minimum() { if (heap.size()

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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