Q1. [15 pts] Write a java program that sorts the following sequence in ascending

Question

Q1. [15 pts] Write a java program that sorts the following sequence in ascending order using in-place heap-sort algorithm. 10 6 15 12 13 17 16 L5 Q2. [25 pts] An airline company uses the formula shown below to determine the priority of passengers on the waiting list for overbooked flights. priority number (A 1000) B C where A is the customers total mileage in the past year B is the number of years in his or her frequent flier program C is a sequence number representing the customers arrival position when he or she booked the flight Given the information of overbooked customers as shown in the following table, write a java program that reads the customers information and determines each customers priority number. The program then builds a priority queue using the priority number and prints a list of waiting customers in priority sequence. Year Name Mileage Sequence 53,000 Bryan Devour 89,000 Amanda Trapp 93,000 Boclan Nguyen 17,000 Sarah Hong

Explanation / Answer

1Q)

import java.util.Scanner;

/* Class HeapSort */
public class HeapSort
{
private static int N;
/* Sort Function */
public static void sort(int arr[])
{   
heap(arr);
for (int i = N; i > 0; i--)
{
swap(arr,0, i);
N = N-1;
maxheap(arr, 0);
}
}   
/* Function to build a heap */   
public static void heap(int arr[])
{
N = arr.length-1;
for (int i = N/2; i >= 0; i--)
maxheap(arr, i);
}
/* Function to swap largest element in heap */
public static void maxheap(int arr[], int i)
{
int left = 2*i ;
int right = 2*i + 1;
int max = i;
if (left <= N && arr[left] > arr[i])
max = left;
if (right <= N && arr[right] > arr[max])
max = right;

if (max != i)
{
swap(arr, i, max);
maxheap(arr, max);
}
}
/* Function to swap two numbers in an array */
public static void swap(int arr[], int i, int j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/* Main method */
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );
System.out.println("Heap Sort Test ");
int n, i;
/* Accept number of elements */
System.out.println("Enter number of integer elements");
n = scan.nextInt();
/* Make array of n elements */
int arr[] = new int[ n ];
/* Accept elements */
System.out.println(" Enter "+ n +" integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
/* Call method sort */
sort(arr);
/* Print sorted Array */
System.out.println(" Elements after sorting ");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}

2Q)

package com.journaldev.collections;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

public class PriorityQueueExample {

   public static void main(String[] args) {
      
       //natural ordering example of priority queue
       Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7);
       Random rand = new Random();
       for(int i=0;i<7;i++){
           integerPriorityQueue.add(new Integer(rand.nextInt(100)));
       }
       for(int i=0;i<7;i++){
           Integer in = integerPriorityQueue.poll();
           System.out.println("Processing Integer:"+in);
       }
      
       Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator);
       addDataToQueue(customerPriorityQueue);
      
       pollDataFromQueue(customerPriorityQueue);
      
   }
  
   public static Comparator<Customer> idComparator = new Comparator<Customer>(){
      
       @Override
       public int compare(Customer c1, Customer c2) {
return (int) (c1.getId() - c2.getId());
}
   };
   private static void addDataToQueue(Queue<Customer> customerPriorityQueue) {
       Random rand = new Random();
       for(int i=0; i<7; i++){
           int id = rand.nextInt(100);
           customerPriorityQueue.add(new Customer(id, "Pankaj "+id));
       }
   }
  
   private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue)
{
       while(true){
           Customer cust = customerPriorityQueue.poll();
           if(cust == null) break;
           System.out.println("Processing Customer with ID="+cust.getId());
       }
   }

}

3Q)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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