TEST ON PRIORITY QUEUES (USING HASHTABLES)
Algorithm HeapSort /*To perform sorting using heaps*/ Input: Array of structures with JobPriority, JobIdentifier, JobOwner NoOfJobs //Number of Jobs Output: Elements are sorted in the ascending order Data structure used: Binary min heap
Implementation: Array of structures HeapArray[i] HeapArray[1] HeapArray[2] HeapArray[3] . . . HeapArray[NoOfJobs]
JobPriority
JobIdentifier
JobOwner
Step 1: Struct JobHeapEntry { int JobIdentifier; char *JobOwner; int JobPriority; }HeapArray[50]; Step 2: Read NoOfJobs Step 3: Repeat through step 5 for i1 to NoOfJobs
Step 4: Read HeapArray[i].JobIdentifier, HeapArray[i].JobOwner, HeapArray[i].JobPriority Step 5: BuildSchedulingQueue(HeapArray,NoOfJobs) Step 6: HeapSorting(HeapArray,HeapSize,NoOfJobs) Step 7: End.
Algorithm BuildSchedulingQueue (HeapArray[], int NoOfJobs) /*To build a job queue for the given array with heap property*/ Output: Queue containing all the jobs to be scheduled. Step 1: HeapSize NoOfJobs Step 2: Repeat through Step 3 for i floor (NoOfJobs/2) downto 1 Step 3: QueueHeapify(HeapArray,i) Step 4: Return
Algorithm QueueHeapify (HeapArray[], int i) /*This is to convert a normal array into array with heap property*/ Output: Min-heapified array Step 1: LeftChild 2 * i Step 2: RightChild 2 * i + 1 Step 3: if ((LeftChild HeapSize) and (HeapArray[LeftChild].JobPriority < HeapArray[i].JobPriority) then Smallest LeftChild else Smallest i t
Step 4: if (RightChild HeapSize) and (HeapArray[LeftChild].JobPriority <
HeapArray[Smallest].JobPriority) then Smallest RightChild Step 5: if (Smallest i)
then Exchange HeapArray[i] and HeapArray[Smallest] QueueHeapify(HeapArray,Smallest)
Step 6: Return
Algorithm HeapSorting(Heaparray[], HeapCurrentSize,NoOfJobs) /*Perform heap sorting in the array*/ Step 1: if(HeapCurrentSize < 1) then Print Heap Underflow else 1.1: Repeat through step 1.6 for i 1 to NoOfJobs 1.2: a[i] HeapArray[1] 1.3: HeapArray[i] HeapArray[HeapCurrentSize] 1.4: HeapCurrentSize -=1 1.5: Print a[i] 1.6: QueueHeapify(HeapArray,1) Step 2: Return
TEST ON PRIORITY QUEUES (USING HASHTABLES)
Name
: M.Latha Karthigaa
Roll Number
: 09
Date of Test
: 12.10.2009
Due date for Demo
: 12.10.2009
Actual date of Demo
: 12.10.2009
Review: 1.
Suggestions from Faculty
: NIL
Date of Review
: NIL
Action taken
: NIL
Demo date
: 12.10.2009
PROGRAM: package heaphashtest; import java.lang.*; import java.io.*; import java.util.*; class JobHeapEntry { int JobIdentifier,JobPriority; String JobOwner; JobHeapEntry() { //empty Constructor } JobHeapEntry(int id,int pri,String own) { JobIdentifier=id; JobPriority=pri; JobOwner=own; } void BuildSchedulingQueue(JobHeapEntry HA[],int NoOfJobs) { int HeapSize=NoOfJobs; for(int i=(NoOfJobs/2);i>=1;i--) QueueHeapify(HA,i,HeapSize); } void HeapSort(JobHeapEntry HA[],int NoOfJobs) { int []a=new int[10]; JobHeapEntry t=new JobHeapEntry(); if(NoOfJobs<1) System.out.println("Heap Underflow"); System.out.print("Elements in Ascending order are:"); for(int i=2;i<=NoOfJobs;i++) { a[i]=HA[1].JobPriority; HA[1]=HA[NoOfJobs]; NoOfJobs--; QueueHeapify(HA,1,NoOfJobs); System.out.print(" "+a[i]); } System.out.print(" "+HA[1].JobPriority); } void QueueHeapify(JobHeapEntry HA1[],int i,int HeapSize) { int LeftChild,RightChild,Smallest=1; JobHeapEntry temp=new JobHeapEntry(); LeftChild=2*i;
RightChild=2*i+1; if(LeftChild<=HeapSize) { if(HA1[LeftChild].JobPriority<HA1[i].JobPriority) { Smallest=LeftChild; } } else Smallest=i; if(RightChild<=HeapSize) { if(HA1[RightChild].JobPriority<HA1[Smallest].JobPriority) { Smallest=RightChild; } } if(Smallest!=i) { temp=HA1[i]; HA1[i]=HA1[Smallest]; HA1[Smallest]=temp; QueueHeapify(HA1,Smallest,HeapSize); } } } public class Main { public static void main(String[] args) throws IOException{ try { int NoOfJobs,Choice,choice_int,del_jobid; JobHeapEntry s=new JobHeapEntry(); JobHeapEntry []HeapArray=new JobHeapEntry[50]; System.out.println("Enter the number of jobs to be inserted in the Heap Array:"); BufferedReader b1=new BufferedReader(new InputStreamReader(System.in)); String Str_NoOfJobs=b1.readLine(); NoOfJobs=Integer.parseInt(Str_NoOfJobs); for(int i=1;i<=NoOfJobs;i++) { System.out.print("Enter the Job Identifier of Job to be inserted:"); BufferedReader b2=new BufferedReader(new InputStreamReader(System.in)); String str_JobId=b2.readLine(); int Id=Integer.parseInt(str_JobId); System.out.print("Enter the Job Owner of Job to be inserted:"); BufferedReader b3=new BufferedReader(new InputStreamReader(System.in)); String str_JobOwn=b3.readLine(); System.out.print("Enter the Job Priority of Job to be inserted:"); BufferedReader b4=new BufferedReader(new InputStreamReader(System.in)); String str_JobPri=b4.readLine(); int Pri=Integer.parseInt(str_JobPri); HeapArray[i]=new JobHeapEntry(Id,Pri,str_JobOwn);
} s.BuildSchedulingQueue(HeapArray,NoOfJobs); for(int i=1;i<=NoOfJobs;i++) { System.out.println(" "+HeapArray[i].JobOwner+" "+HeapArray[i].JobIdentifier+" "+HeapArray[i].JobPriority); } do { System.out.println("MENU\n_____\n1.HeapSort"); System.out.println("2.Exit the Scheduling process"); System.out.println("Enter your choice:"); BufferedReader br_choice=new BufferedReader(new InputStreamReader(System.in)); String str_choice=br_choice.readLine(); Choice=Integer.parseInt(str_choice); switch(Choice) {
case 1: s.HeapSort(HeapArray,NoOfJobs); break; case 2: return; } System.out.println("Do you want to continue(1/0)?"); BufferedReader gg=new BufferedReader(new InputStreamReader(System.in)); String ch=gg.readLine(); choice_int=Integer.parseInt(ch); } while(choice_int==1); } catch(Exception e) { System.out.println(e); } } } RESULT: TEST CASE 1: Enter the number of jobs to be inserted in the Heap Array: 6 Enter the Job Identifier of Job to be inserted:1 Enter the Job Owner of Job to be inserted:aaa Enter the Job Priority of Job to be inserted:44 Enter the Job Identifier of Job to be inserted:2 Enter the Job Owner of Job to be inserted:bbb
Enter the Job Priority of Job to be inserted:66 Enter the Job Identifier of Job to be inserted:8 Enter the Job Owner of Job to be inserted:ccc Enter the Job Priority of Job to be inserted:43 Enter the Job Identifier of Job to be inserted:9 Enter the Job Owner of Job to be inserted:ddd Enter the Job Priority of Job to be inserted:52 Enter the Job Identifier of Job to be inserted:10 Enter the Job Owner of Job to be inserted:eee Enter the Job Priority of Job to be inserted:76 Enter the Job Identifier of Job to be inserted:12 Enter the Job Owner of Job to be inserted:fff Enter the Job Priority of Job to be inserted:25 MENU ______ 1. Heap Sort 2. Exit the Scheduling process Enter your choice: 1 The elements (Job Priorities) after sorting: 25 TEST CASE 2: Enter the number of jobs to be inserted in the Heap Array: 0 Heap Underflow 43 44 52 56 76
