You will implement a heap from the following interface: public interface Heap<V
ID: 3689907 • Letter: Y
Question
You will implement a heap from the following interface:
public interface Heap<V extends Comparable<V>> {
public void add(V value);
public V[] toArray(V[] array);
public V remove();
public void fromArray(V[] array);
public V[] getSortedContents(V[] array);
}
However, the Heap should be implemented as a Node Heap, that is, the internal implementation should be a tree instead of an array. The getSortedContents method should, internally, transform the heap into its array representation, and the perform Heap-Sort on it, then return the array as the result. All heap operations should mantain the same worst-case runtime complexity discussed in class for the array version.
You will create a program with the following functionality:
You will create a table-assgining application for a restaurant. The application takes as input customer data as they arrive and outputs the next person to be seated. When a table becomes available, the seating host ask the program for the next customer to be seated. The restaurant has the following class of customers, listed in order of priority:VIPsAdvance Call: customers who called in advance.Seniors.Veterans.Large Groups (more than 4).Families with children.Everyone else.You will create a class that will represent customers, and should at least contain the name to call out, and the priority class. You will create it so that instances can be compared based on their priority.Your program will use a max-Heap to store the customer data, structured based on their priority class. When the host inputs a new customer it is inserted into the heap. When the host asks for the next to be seated, the next customer is extracted from the heap based on their priority class.
Explanation / Answer
MainApp.java
public class MainApp {
public static void main(String[] args){
RestuantQueue.startApp();
}
}
Customer.java
public class Customer implements Comparable<Customer>{
protected String groupName;
protected boolean hasVip = false;
protected boolean hasReservation = false;
protected boolean hasSeniors = false;
protected boolean hasVeterans = false;
protected int groupSize = 1;
protected boolean hasChildren = false;
protected int priority;
public Customer(int size, String name, boolean vip, boolean reservation, boolean senoirs, boolean veterans, boolean children){
groupSize = size;
groupName = name;
hasVip = vip;
hasReservation = reservation;
hasSeniors = senoirs;
hasVeterans = veterans;
hasChildren = children;
calcPriority();
}
public Customer(int size, String name){
groupSize = size;
groupName = name;
calcPriority();
}
public void setVipStatus(boolean vip){
hasVip = vip;
calcPriority();
}
public void setReservationStatus(boolean reservation){
hasReservation = reservation;
calcPriority();
}
public void setSeniorStatus(boolean senior){
hasSeniors = senior;
calcPriority();
}
public void setVeteranStatus(boolean veteran){
hasVeterans = veteran;
calcPriority();
}
public void setChilderenStatus(boolean children){
hasChildren = children;
calcPriority();
}
public void setGroupSize(int size){
groupSize = size;
calcPriority();
}
private void calcPriority() {
if(hasVip)
priority = 7;
else if(hasReservation)
priority = 6;
else if(hasSeniors)
priority = 5;
else if(hasVeterans)
priority = 4;
else if(groupSize > 4)
priority = 3;
else if(hasChildren)
priority = 2;
else
priority = 1;
}
public int compareTo(Customer customer) {
if(this.priority > customer.priority)
return 1;
else if(this.priority < customer.priority)
return -1;
else
return 0;
}
public String toString(){
String str = groupName + " - Party of: " + groupSize;
return str;
}
//Accessors
public boolean getVipStatus(){
return hasVip;
}
public boolean getReservationStatus(){
return hasReservation;
}
public boolean getSeniorStatus(){
return hasSeniors;
}
public boolean getVeteranStatus(){
return hasVeterans;
}
public boolean getChilderenStatus(){
return hasChildren;
}
public int getGroupSize(){
return groupSize;
}
public String getGroupName(){
return groupName;
}
}
Heap.java
public interface Heap <V extends Comparable<V>>{
public void add(V value);
public V[] toArray();
public V remove();
public void fromArray(V[] array);
public V[] getSortedContents();
}
NodeHeap.java
import java.util.ArrayList;
public class NodeHeap<V extends Comparable<V>> implements Heap<V> {
protected int heapSize = 0;
protected Node root;
@Override
public void add(V value) {
Node newNode = new Node();
newNode.value = value;
if(heapSize == 0){
root = newNode;
heapSize++;
}
else{
Node addPos = getAddNodePos();
if(addPos.leftChild == null){
addPos.leftChild = newNode;
newNode.parent = addPos;
}
else{
addPos.rightChild = newNode;
newNode.parent = addPos;
}
heapSize++;
siftUp(newNode);
}
}
private Node getAddNodePos(){
ArrayList<Node> queue = new ArrayList<Node>();
queue.add(root);
Node currentNode = root;
while(currentNode.leftChild != null || currentNode.rightChild != null){
currentNode = queue.remove(0);
if(currentNode.leftChild != null)
queue.add(currentNode.leftChild);
else
return currentNode;
if(currentNode.rightChild != null)
queue.add(currentNode.rightChild);
else
return currentNode;
}
return currentNode;
}
private void siftUp(Node node){
Node count = node;
int heapLevels = (int) ((Math.log(heapSize + 1)) / Math.log(2));
for(int i = heapLevels; i >= 0; i--){
if(count.parent != null && count.parent.value.compareTo(count.value) < 0){
count = swap(count, count.parent);
if(count.parent != null && count.parent.parent == null)
count.parent = root;
}
}
if(count.parent != null && count.parent.value.compareTo(count.value) < 0){
count = swap(count, count.parent);
}
if(count.parent == null){
root = count;
}
}
private Node swap(Node child, Node parent){
Node tmp = new Node();
tmp.value = child.value;
child.value = parent.value;
parent.value = tmp.value;
return parent;
}
@SuppressWarnings("unchecked")
@Override
public V[] toArray() {
V[] tmp = (V[])java.lang.reflect.Array.newInstance(root.value.getClass(), heapSize);
int counter = 0;
ArrayList<Node> queue = new ArrayList<Node>();
queue.add(root);
Node currentNode = root;
while(currentNode != null){
currentNode = queue.remove(0);
tmp[counter] = currentNode.value;
counter++;
if(currentNode.leftChild == null){
break;
}
queue.add(currentNode.leftChild);
if(currentNode.rightChild == null)
break;
queue.add(currentNode.rightChild);
}
while(queue.size() != 0){
tmp[counter] = queue.remove(0).value;
counter++;
}
return tmp;
}
@Override
public V remove() {
Node tmp = root;
tmp.leftChild = root.leftChild;
tmp.rightChild = root.rightChild;
Node newRoot = getRemovePos();
// System.out.println(root.value);
if(newRoot.parent != null){
root = newRoot;
if(root.parent.leftChild == root)
root.parent.leftChild = null;
else if(root.parent.rightChild == root)
root.parent.rightChild = null;
else{
root.rightChild = null;
root = root.leftChild;
}
root.leftChild = tmp.leftChild;
root.rightChild = tmp.rightChild;
}
siftDown(newRoot);
heapSize--;
return tmp.value;
}
private void siftDown(Node node) {
Node swapNode = node;
Node parent = node;
int heapLevels = (int) ((Math.log(heapSize) + 1) / Math.log(2));
for(int i = heapLevels; i > 0; i--){
if(parent.leftChild != null && parent.leftChild.value.compareTo(swapNode.value) > 0)
swapNode = parent.leftChild;
if(parent.rightChild != null && parent.rightChild.value.compareTo(swapNode.value) > 0)
swapNode = parent.rightChild;
parent = swap(parent, swapNode);
}
}
private Node getRemovePos(){
ArrayList<Node> queue = new ArrayList<Node>();
queue.add(root);
Node currentNode = root;
while(queue.get(0) != null){
currentNode = queue.remove(0);
queue.add(currentNode.leftChild);
queue.add(currentNode.rightChild);
}
return currentNode;
}
//REDO
@Override
public void fromArray(V[] array) {
for(int i = 0; i < array.length; i++){
this.add(array[i]);
}
}
@Override
public V[] getSortedContents() {
V[] array = this.toArray();
int end = array.length - 1;
heapifiy(array);
V tmp = array[end];
// System.out.println(array[0]);
array[end] = array[0];
array[0] = tmp;
for(int i = end; i > 0; i--){
tmp = array[i];
// System.out.println(array[0]);
array[i] = array[0];
array[0] = tmp;
siftDown(array, 0, i - 1);
}
return array;
}
private void siftDown(V[] array, int begIndex, int endIndex){
int swapIndex = begIndex;
int leftChildIndex = (2 * begIndex) + 1;
int rightChildIndex = (2 * begIndex) + 2;
if(leftChildIndex <= endIndex){
V leftChild = array[leftChildIndex];
if(leftChild.compareTo(array[begIndex]) > 0)
swapIndex = leftChildIndex;
}
if(rightChildIndex <= endIndex){
V rightChild = array[rightChildIndex];
if(rightChild.compareTo(array[swapIndex]) > 0)
swapIndex = rightChildIndex;
}
}
private void heapifiy(V[] array) {
for(int i = array.length/2; i >= 0; i--){
siftDown(array, i);
}
}
private void siftDown(V[] array, int index){
int swapIndex = index;
int leftChildIndex = (2 * index) + 1;
int rightChildIndex = (2 * index) + 2;
if(leftChildIndex < array.length){
V leftChild = array[leftChildIndex];
if(leftChild.compareTo(array[index]) > 0)
swapIndex = leftChildIndex;
}
if(rightChildIndex < array.length){
V rightChild = array[rightChildIndex];
if(rightChild.compareTo(array[swapIndex]) > 0)
swapIndex = rightChildIndex;
}
if(swapIndex != index){
V tmp = array[index];
array[index] = array[swapIndex];
array[swapIndex] = tmp;
siftDown(array, swapIndex);
}
}
public String toString(){
String str = "";
V[] tmp = toArray();
for(int i = 0; i < tmp.length; i++){
if(tmp[i] != null)
str = str.concat(" | " + tmp[i] + " | ");
}
return str;
}
class Node{
Node leftChild;
Node rightChild;
Node parent = null;
V value;
}
}
PriorityQueue.java
public class PriorityQueue<V extends Comparable<V>> {
NodeHeap<V> maxHeap = new NodeHeap<V>();
public void enqueue(V item){
maxHeap.add(item);
}
public V dequeue(){
return maxHeap.remove();
}
public V peek(){
V[] array = maxHeap.toArray();
return array[0];
}
public int size(){
return maxHeap.heapSize;
}
}
RestuantQueue.java
import java.util.Scanner;
//TODO validate input
public class RestuantQueue {
private static PriorityQueue<Customer> queue = new PriorityQueue<Customer>();
private static Scanner kb = new Scanner(System.in);
public static void startApp() {
printMenu();
}
private static void printMenu() {
try{
int userInput = 0;
do{
printUI();
userInput = kb.nextInt();
kb.nextLine();
calcInput(userInput);
}while(userInput != 4);
}
catch(Exception e){
System.out.println(" oops something went wrong, try again. ");
kb.nextLine();
printMenu();
}
}
private static void calcInput(int input) {
if(input == 1){
addCustomer();
}
else if(input == 2){
removeCustomer();
}
else if(input == 3){
peekCustomer();
}
else if(input == 4){
System.out.println("Now Exiting... Have a Nice day!");
}
else
System.out.println("UNRECOGNIZED COMMAND. Please try again.");
}
private static void addCustomer(){
boolean vip, reservation, senior, veteran, children;
int input = 0;
System.out.print("Please enter the group size: ");
int groupSize = kb.nextInt();
kb.nextLine();
System.out.print("Please enter the group name: ");
String name = kb.nextLine();
System.out.println("Is the customer a VIP? (1 = yes. 2 = no) ");
input = kb.nextInt();
if(input == 1)
vip = true;
else
vip = false;
kb.nextLine();
System.out.println("Does the customer have a reservation? (1 = yes. 2 = no) ");
input = kb.nextInt();
if(input == 1)
reservation = true;
else
reservation = false;
kb.nextLine();
System.out.println("Is the customer a Senior(Age 55+)? (1 = yes. 2 = no) ");
input = kb.nextInt();
if(input == 1)
senior = true;
else
senior = false;
kb.nextLine();
System.out.println("Is the customer a Veteran? (1 = yes. 2 = no) ");
input = kb.nextInt();
if(input == 1)
veteran = true;
else
veteran = false;
kb.nextLine();
System.out.println("Does the customer have children? (1 = yes. 2 = no) ");
input = kb.nextInt();
if(input == 1)
children = true;
else
children = false;
kb.nextLine();
Customer customer = new Customer(groupSize, name, vip, reservation, senior, veteran, children);
queue.enqueue(customer);
}
private static void removeCustomer() {
System.out.println(" A table for " + queue.dequeue() + " is now ready");
}
private static void peekCustomer() {
System.out.println(" " + queue.peek() + " is the next customer that will be served");
}
private static void printUI() {
System.out.println("Use the following to add or remove customers to the waiting list:");
System.out.println(" 1.) Add customer to waiting list.");
System.out.println(" 2.) Remove customer to waiting list.");
System.out.println(" 3.) View next customer on the waiting list.");
System.out.println();
System.out.println(" 4.) Exit App.");
System.out.println();
System.out.print("Enter Selection Now: ");
}
}
sample output
Use the following to add or remove customers to the waiting list:
1.) Add customer to waiting list.
2.) Remove customer to waiting list.
3.) View next customer on the waiting list.
4.) Exit App.
Enter Selection Now: 1
Please enter the group size: 3
Please enter the group name: family
Is the customer a VIP? (1 = yes. 2 = no)
2
Does the customer have a reservation? (1 = yes. 2 = no)
2
Is the customer a Senior(Age 55+)? (1 = yes. 2 = no)
2
Is the customer a Senior(Age 55+)? (1 = yes. 2 = no)
1
Is the customer a Veteran? (1 = yes. 2 = no)
2
Does the customer have children? (1 = yes. 2 = no)
1
Use the following to add or remove customers to the waiting list:
1.) Add customer to waiting list.
2.) Remove customer to waiting list.
3.) View next customer on the waiting list.
4.) Exit App.
Enter Selection Now: 3
family - Party of: 3 is the next customer that will be served
Use the following to add or remove customers to the waiting list:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.