Objective: Maxheap priority queue Download inventory.txt, MaxHeap.java Default J
ID: 3776157 • Letter: O
Question
Objective: Maxheap priority queue
Download inventory.txt, MaxHeap.java
Default Java.util.PriorityQueue is Minimum Queue.
Write the main java program to read all records from inventory.txt to build a Maxheap Queue use both MaxHeap.java and java.util.PriorityQueue.
Print both Heap-queues and then remove the Max from Maxheap queue.
The order of the priority is the string value of the input records.
Given Codes:
/** Source code example for "A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/
import java.lang.Comparable;
/** Max-heap implementation */
public class MaxHeap> {
private E[] Heap; // Pointer to the heap array
private int size; // Maximum size of the heap
private int n; // Number of things in heap
/** Constructor supporting preloading of heap contents */
public MaxHeap(E[] h, int num, int max)
{ Heap = h; n = num; size = max; buildheap(); }
/** @return Current size of the heap */
public int heapsize() { return n; }
/** @return True if pos a leaf position, false otherwise */
public boolean isLeaf(int pos)
{ return (pos >= n/2) && (pos < n); }
/** @return Position for left child of pos */
public int leftchild(int pos) {
assert pos < n/2 : "Position has no left child";
return 2*pos + 1;
}
/** @return Position for right child of pos */
public int rightchild(int pos) {
assert pos < (n-1)/2 : "Position has no right child";
return 2*pos + 2;
}
/** @return Position for parent */
public int parent(int pos) {
assert pos > 0 : "Position has no parent";
return (pos-1)/2;
}
/** Insert val into heap */
public void insert(E val) {
assert n < size : "Heap is full";
int curr = n++;
Heap[curr] = val; // Start at end of heap
// Now sift up until curr's parent's key > curr's key
while ((curr != 0) &&
(Heap[curr].compareTo(Heap[parent(curr)]) > 0)) {
DSutil.swap(Heap, curr, parent(curr)); // exchange content of Heap[curr] with Heap[parent(curr)]
curr = parent(curr);
}
}
/** Heapify contents of Heap */
public void buildheap()
{ for (int i=n/2 - 1; i>=0; i--) siftdown(i); }
/** Put element in its correct place */
private void siftdown(int pos) {
assert (pos >= 0) && (pos < n) : "Illegal heap position";
while (!isLeaf(pos)) {
int j = leftchild(pos);
if ((j<(n-1)) && (Heap[j].compareTo(Heap[j+1]) < 0))
j++; // j is now index of child with greater value
if (Heap[pos].compareTo(Heap[j]) >= 0) return;
DSutil.swap(Heap, pos, j);
pos = j; // Move down
}
}
/** Remove and return maximum value */
public E removemax() {
assert n > 0 : "Removing from empty heap";
DSutil.swap(Heap, 0, --n); // Swap maximum with last value
if (n != 0) // Not on last element
siftdown(0); // Put new heap root val in correct place
return Heap[n];
}
/** Remove and return element at specified position */
public E remove(int pos) {
assert (pos >= 0) && (pos < n) : "Illegal heap position";
if (pos == (n-1)) n--; // Last element, no work to be done
else
{
DSutil.swap(Heap, pos, --n); // Swap with last value
// If we just swapped in a big value, push it up
while ((pos > 0) &&
(Heap[pos].compareTo(Heap[parent(pos)]) > 0)) {
DSutil.swap(Heap, pos, parent(pos));
pos = parent(pos);
}
if (n != 0) siftdown(pos); // If it is little, push down
}
return Heap[n];
}
}
/** Source code example for "A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/
import java.util.*;
import java.math.*;
/** A bunch of utility functions. */
class DSutil<E> {
/** Swap two Objects in an array
@param A The array
@param p1 Index of one Object in A
@param p2 Index of another Object A
*/
public static <E> void swap(E[] A, int p1, int p2) {
E temp = A[p1];
A[p1] = A[p2];
A[p2] = temp;
}
/** Randomly permute the Objects in an array.
@param A The array
*/
// int version
// Randomly permute the values of array "A"
static void permute(int[] A) {
for (int i = A.length; i > 0; i--) // for each i
swap(A, i-1, DSutil.random(i)); // swap A[i-1] with
} // a random element
public static void swap(int[] A, int p1, int p2) {
int temp = A[p1];
A[p1] = A[p2];
A[p2] = temp;
}
/** Randomly permute the values in array A */
static <E> void permute(E[] A) {
for (int i = A.length; i > 0; i--) // for each i
swap(A, i-1, DSutil.random(i)); // swap A[i-1] with
} // a random element
/** Initialize the random variable */
static private Random value = new Random(); // Hold the Random class object
/** Create a random number function from the standard Java Random
class. Turn it into a uniformly distributed value within the
range 0 to n-1 by taking the value mod n.
@param n The upper bound for the range.
@return A value in the range 0 to n-1.
*/
static int random(int n) {
return Math.abs(value.nextInt()) % n;
}
}
Text File:
CV06C1250B
MA06C1042A
MA06C1043A
SU04D1043B
SU04D1042B
CV06C1250A
CV06D1250B
HY09F3014A
KI04D1297A
Explanation / Answer
/*output
---------------Maxheap---------------------
Max : [CV06C1250B, MA06C1042A, MA06C1043A, SU04D1043B, SU04D1042B, CV06C1250A, CV06D1250B, HY09F3014A, KI04D1297A]
Removing [CV06C1250B, MA06C1042A, MA06C1043A, SU04D1043B, SU04D1042B, CV06C1250A, CV06D1250B, HY09F3014A, KI04D1297A]
*/
package com.heap;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;
public class heap {
public static void main(String[] args) {
List<String> asList = new ArrayList<String>();
try (BufferedReader br = new BufferedReader(new FileReader("C:\ArunTest\temp\test.txt")))
{
String sCurrentLine;
while ((sCurrentLine = br.readLine()) != null) {
asList.add(sCurrentLine);
}
} catch (IOException e) {
e.printStackTrace();
}
testHeapUsingPriorityQueue(asList);
}
static void testHeapUsingPriorityQueue(List<String> asList){
/* PriorityQueue<String> minheap=new PriorityQueue<String>(1,new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if(o1.equals(o2))
return 0;
else return -1;
}
});
minheap.add(asList.toString());
System.out.println("Minheap---------------------");
System.out.println(Arrays.toString(minheap.toArray()));
for (Iterator iterator = minheap.iterator(); iterator.hasNext();) {
System.out.println("Min : "+minheap.element());
System.out.println("Removing " + minheap.element());
minheap.remove();
}
*/
//create a new object and add a custom comparator that provides the "MaxHeap" behaviour.
PriorityQueue<String> maxheap=new PriorityQueue<String>(1,new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if(o1.equals(o2))
return 0;
else if(o1.length()>o2.length())
{
return 1;
}else
return -1;
}
});
System.out.println("---------------Maxheap---------------------");
//add elements
maxheap.add(asList.toString());
// System.out.println(Arrays.toString(maxheap.toArray()));
for (Iterator iterator = maxheap.iterator(); iterator.hasNext();) {
System.out.println("Max : "+maxheap.element());
System.out.println("Removing " + maxheap.element()+" ");
maxheap.remove();
}
}
}
//if you want min heap, then uncomment the code in above code
/*
Create a text file at location C:\ArunTest\temp\test.txt
CV06C1250B
MA06C1042A
MA06C1043A
SU04D1043B
SU04D1042B
CV06C1250A
CV06D1250B
HY09F3014A
KI04D1297A
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.