Please implement MyMaxPriorityQueue below. Thanks
import net.datastructures.Entry;
public class MyMaxPriorityQueue<K, V> {
@Override
public int size() {
// TODO Auto-generated method
stub
return 0;
}
@Override
public Entry<K, V> insert(K key, V value) throws
IllegalArgumentException {
// TODO Auto-generated method
stub
return null;
}
@Override
public Entry<K, V> max() {
// TODO Auto-generated method
stub
return null;
}
@Override
public Entry<K, V> removeMax() {
// TODO Auto-generated method
stub
return null;
}
}
***Note that for a precise solution, you need to provide the Entry<K, V> class too.
For time being, I am providing a sample solution below.
CODE
==================
import java.util.Vector;
import java.lang.Exception;
class Entry <K extends Comparable<K>, V extends Comparable<V>>
implements Comparable<Entry<K, V>>{
K key;
V value;
public Entry(K k, V v) {
key = k;
value = v;
}
@Override
public int compareTo(Entry<K, V> o) {
return value.compareTo(o.value);
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Entry [key=" + key + ", value=" + value + "]";
}
}
// Class for implementing Priority Queue
public class MyMaxPriorityQueue<K extends Comparable<K>, V extends Comparable<V>> implements Comparable<Entry<K, V>>{
// vector to store heap elements
private Vector<Entry<K, V>> A;
public MyMaxPriorityQueue(int capacity)
{
A = new Vector<Entry<K, V>>(capacity);
}
// return parent of A.get(i)
private int parent(int i) {
// if i is already a root node
if (i == 0)
return 0;
return (i - 1) / 2;
}
// return left child of A.get(i)
private int LEFT(int i)
{
return (2 * i + 1);
}
// return right child of A.get(i)
private int RIGHT(int i)
{
return (2 * i + 2);
}
// swap values at two indexes
void swap(int x, int y)
{
// swap with child having greater value
Entry<K, V> temp = A.get(x);
A.setElementAt(A.get(y), x);
A.setElementAt(temp, y);
}
// Recursive Heapify-down procedure. Here the node at index i
// and its two direct children violates the heap property
private void heapify_down(int i)
{
// get left and right child of node at index i
int left = LEFT(i);
int right = RIGHT(i);
int largest = i;
// compare A.get(i) with its left and right child
// and find largest value
if (left < size() && A.get(left).value.compareTo(A.get(i).value) > 1)
largest = left;
if (right < size() && A.get(right).compareTo(A.get(largest)) > 1)
largest = right;
if (largest != i)
{
// swap with child having greater value
swap(i, largest);
// call heapify-down on the child
heapify_down(largest);
}
}
// Recursive Heapify-up procedure
private void heapify_up(int i)
{
// check if node at index i and its parent violates
// the heap property
if (i > 0 && A.get(parent(i)).compareTo(A.get(i)) < 1)
{
// swap the two if heap property is violated
swap(i, parent(i));
// call Heapify-up on the parent
heapify_up(parent(i));
}
}
// return size of the heap
public int size()
{
return A.size();
}
// check if heap is empty or not
public Boolean isEmpty()
{
return A.isEmpty();
}
// insert specified key into the heap
public Entry<K, V> insert(K key, V value) throws IllegalArgumentException {
if(key == null)
throw new IllegalArgumentException("Illegal Argument key!");
Entry<K, V> e = new Entry<>(key, value);
// insert the new element to the end of the vector
A.addElement(e);
// get element index and call heapify-up procedure
int index = size() - 1;
heapify_up(index);
return e;
}
// function to remove and return element with highest priority
// (present at root). It returns null if queue is empty
public Entry<K, V> removeMax() {
try {
// if heap is empty, throw an exception
if (size() == 0)
throw new Exception("Index is out of range (Heap underflow)");
// element with highest priority
Entry<K, V> root = A.firstElement(); // or A.get(0);
// replace the root of the heap with the last element of the vector
A.setElementAt(A.lastElement(), 0);
A.remove(size()-1);
// call heapify-down on root node
heapify_down(0);
// return root element
return root;
}
// catch and print the exception
catch (Exception ex) {
System.out.println(ex);
return null;
}
}
// function to return, but does not remove, element with highest priority
// (present at root). It returns null if queue is empty
public Entry<K, V> max() {
try {
// if heap has no elements, throw an exception
if (size() == 0)
throw new Exception("Index out of range (Heap underflow)");
// else return the top (first) element
return A.firstElement(); // or A.get(0);
}
// catch the exception and print it, and return null
catch (Exception ex) {
System.out.println(ex);
return null;
}
}
// Program for Max Heap Implementation in Java
public static void main (String[] args)
{
// create a Priority Queue of initial capacity 10
// Priority of an element is decided by element's value
MyMaxPriorityQueue<Integer, Integer> pq = new MyMaxPriorityQueue<>(10);
// insert three integers
pq.insert(0, 3);
pq.insert(1, 2);
pq.insert(2, 15);
// print Priority Queue size
System.out.println("Priority Queue Size is " + pq.size());
// search 2 in Priority Queue
Integer searchKey = 2;
if (pq.isEmpty())
System.out.println("Queue is Empty");
System.out.println("\nCalling remove operation on an empty heap");
System.out.println("Element with highest priority is " + pq.removeMax());
System.out.println("\nCalling peek operation on an empty heap");
System.out.println("Element with highest priority is " + pq.max());
// again insert three integers
pq.insert(9, 5);
pq.insert(7, 4);
pq.insert(5, 45);
System.out.println("\n\nElement with highest priority is " + pq.removeMax());
System.out.println("Element with highest priority is " + pq.max());
}
@Override
public int compareTo(Entry<K, V> o) {
// TODO Auto-generated method stub
return 0;
}
}
OUTPUT
==================
Please implement MyMaxPriorityQueue below. Thanks import net.datastructures.Entry; public class MyMaxPriorityQueue<K, V> { @Override public...
Implement the missing methods in java! Thanks! import java.util.Iterator; import java.util.NoSuchElementException; public class HashTableOpenAddressing<K, V> implements DictionaryInterface<K, V> { private int numEntries; private static final int DEFAULT_CAPACITY = 5; private static final int MAX_CAPACITY = 10000; private TableEntry<K, V>[] table; private double loadFactor; private static final double DEFAULT_LOAD_FACTOR = 0.75; public HashTableOpenAddressing() { this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); } public HashTableOpenAddressing(int initialCapacity, double loadFactorIn) { numEntries = 0; if (loadFactorIn <= 0 || initialCapacity <= 0) { throw new IllegalArgumentException("Initial capacity and load...
//MultiValuedTreeMap.java import java.util.Iterator; import java.util.LinkedList; import java.util.TreeMap; //import java.util.ArrayList; public class MultiValuedTreeMap<K, V> extends TreeMap<K, LinkedList<V>> implements Iterable<Pair<K, V>> { private static final long serialVersionUID = -6229569372944782075L; public void add(K k, V v) { // Problem 1 method // empty linked list, with key=k if (!containsKey(k)) { put(k, new LinkedList<V>()); } // adding v to the linked list associated with key k get(k).add(v); } public V removeFirst(K k)...
package model; import java.util.Iterator; /** * This class implements interface PriorityList<E> to represent a generic * collection to store elements where indexes represent priorities and the * priorities can change in several ways. * * This collection class uses an Object[] data structure to store elements. * * @param <E> The type of all elements stored in this collection */ // You will have an error until you have have all methods // specified in interface PriorityList included inside this...
import java.util.Scanner; public class TriangleMaker { public static void main(String[] args) { // TODO Auto-generated method stub System.out.println("Welcome to the Triangle Maker! Enter the size of the triangle."); Scanner keyboard = new Scanner(System.in); int size = keyboard.nextInt(); for (int i = 1; i <= size; i++) { for (int j = 0; j < i; j++) { System.out.print("*"); } System.out.println(); } for (int...
I need some help with some homework questions. How would I implement the to-do's? ----------------------------------------------------------------------------------------------------------------------------------------------------------- AbstractArrayHeap.Java package structures; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.NoSuchElementException; public abstract class AbstractArrayHeap<P, V> { protected final ArrayList<Entry<P, V>> heap; protected final Comparator<P> comparator; protected AbstractArrayHeap(Comparator<P> comparator) { if (comparator == null) { throw new NullPointerException(); } this.comparator = comparator; heap = new ArrayList<Entry<P, V>>(); } public final AbstractArrayHeap<P, V> add(P priority, V value) { if (priority == null || value...
ANNOTATE BRIEFLY LINE BY LINE THE FOLLOWING CODE: package shop.data; import junit.framework.Assert; import junit.framework.TestCase; public class DataTEST extends TestCase { public DataTEST(String name) { super(name); } public void testConstructorAndAttributes() { String title1 = "XX"; String director1 = "XY"; String title2 = " XX "; String director2 = " XY "; int year = 2002; Video v1 = Data.newVideo(title1, year, director1); Assert.assertSame(title1, v1.title()); Assert.assertEquals(year, v1.year()); Assert.assertSame(director1, v1.director()); Video v2 = Data.newVideo(title2, year, director2); Assert.assertEquals(title1, v2.title()); Assert.assertEquals(director1, v2.director()); } public void testConstructorExceptionYear()...
import java.util.Iterator; import java.util.LinkedList; import java.util.TreeMap; import java.util.ArrayList; public class MultiValuedTreeMap<K, V> extends TreeMap<K, LinkedList<V>> implements Iterable<Pair<K, V>> { private static final long serialVersionUID = -6229569372944782075L; public void add(K k, V v) { if (!containsKey(k)) { put(k, new LinkedList<V>()); } get(k).add(v); } public V removeFirst(K k) { if (!containsKey(k)) { return null; } V value = get(k).removeFirst(); if (get(k).isEmpty()) { super.remove(k); } return value; }...
I need help with todo line please public class LinkedList { private Node head; public LinkedList() { head = null; } public boolean isEmpty() { return head == null; } public int size() { int count = 0; Node current = head; while (current != null) { count++; current = current.getNext(); } return count; } public void add(int data) { Node newNode = new Node(data); newNode.setNext(head); head = newNode; } public void append(int data) { Node newNode = new Node(data);...
package algs24; import stdlib.StdIn; import stdlib.StdOut; /** * The <tt>PtrHeap</tt> class is the priorityQ class from Question 2.4.24. * It represents a priority queue of generic keys. * * It supports the usual <em>insert</em> and <em>delete-the-maximum</em> * operations, along with methods for peeking at the maximum key, * testing if the priority queue is empty, and iterating through * the keys. * For additional documentation, see <a href="http://algs4.cs.princeton.edu/24pq">Section 2.4</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne....
TreeNode.java public class TreeNode { public int key; public TreeNode p; public TreeNode left; public TreeNode right; public TreeNode () { p = left = right = null; } public TreeNode (int k) { key = k; p = left = right = null; } } BinarySearchTree.java public class BinarySearchTree { public TreeNode root; public BinarySearchTree () { root...