"FOR ANSROHAN"

HONOR CODE

COMP-3040-02

Data Structures

Assignment-6

Due on 10/31/2018

I pledge my honor that I have neither given nor received aid on this work.

Do not sign until after you have completed your assignment.

Name: Signature:

COMP3040 Data Structures Assignment 6

Due 10/31/2018

1. (20 pts) Are the following arrays heaps? Why or why not?

(a)

95 77 43 66 64 25 44 11 10 47

(b)

20 27 56 56 44 77 91 82 98 73

2. (30 pts) Given an heap array: 99 77 81 45 11 16 30 40 22 1,

a) draw the heap (tree)

b) draw the heap (tree) after max node (99) is removed from the original heap

c) draw the heap (tree) after a node 77 is inserted to the original heap

d) draw the heap (tree) after node 22 is changed to 85 on the original heap

3. (20 pts) Execute program maxHeap.java and heapApplication.java:

a) Insert the nodes listed in 1(a) to the heap.

b) Display the heap array and compare it with the array in 1(a). What do you find out?

4. (30) Write the class for max-heap of Employee records. (The Employee class is given below. The

employee seqNo is used as key). The program must contain the following 5 operations:

 Build a heap by a given array of Employee.

 Extract an employee with the maximum seqNo from the heap.

 Insert a new employee record into the heap.

 Heapsort a heap by employee seqNo.

 Print the heap with all employee’s seqNo and salary

Also, write a Main method to test your program as follows:

 Create an array A of Employee records. Create an empty max-heap. Assign 10 employee

records one by one into the array A in the following order:

record1: name1, 1048

record2: name2, 1078

record3: name3, 1065

record4: name4, 1088

record5: name5, 1098

record6: name6, 1099

record7: name7, 1054

record8: name8, 1062

record9: name9, 2000

record10: ame10, 1085

 Build the max-heap from above array of Employee, and print the heap.

 Extract an employee record with the maximum SeqNo, and print the heap.

 Insert a new employee record into the heap, and print the heap.

public class Employee

{

public int id;

public String name;

public double salary;

public void Input()

{

System.out.println("Enter name: ");

name = new Scanner(System.in).nextLine();

System.out.println("Enter ID: ");

id = Integer.parseInt(new Scanner(System.in).nextLine());

System.out.println("Enter Salary: ");

salary = Double.parseDouble(new Scanner(System.in).nextLine());

}

public void Output()

{

System.out.printf("Name: %1$s, ID: %2$s, Grade: %3$s ", name, id, salary);

}

public String toString()

{

return String.format("[Name: %1$s, ID: %2$s, Grade: %3$s]", name, id, salary);

}

}

A sample output may look like the following:

Enter first letter of show, insert, remove, update, q to quit: s

heapArray: [name9|2000|41324.00] [name6|1099|48999.00] [name5|1098|81123.00] [na

me4|1088|91110.00] [name10|1085|71000.00] [name3|1065|45691.00] [name7|1054|6722

3.00] [name1|1048|65435.00] [name8|1062|71112.00] [name2|1078|82221.00]

................................................................

[name9|2000|41324.00]

[name6|1099|48999.00] [name5|1098|81123.00]

[name4|1088|91110.00] [name10|1085|71000.00] [

name3|1065|45691.00] [name7|1054|67223.00]

[name1|1048|65435.00] [name8|1062|71112.00] [name2|1078|82221.00]

................................................................

Enter first letter of show, insert, remove, update, q to quit: r

Enter first letter of show, insert, remove, update, q to quit: s

heapArray: [name6|1099|48999.00] [name4|1088|91110.00] [name5|1098|81123.00] [na

me2|1078|82221.00] [name10|1085|71000.00] [name3|1065|45691.00] [name7|1054|6722

3.00] [name1|1048|65435.00] [name8|1062|71112.00]

................................................................

[name6|1099|48999.00]

[name4|1088|91110.00] [name5|1098|8

1123.00]

[name2|1078|82221.00] [name10|1085|71000.00] [

name3|1065|45691.00] [name7|1054|67223.00]

[name1|1048|65435.00] [name8|1062|71112.00]

................................................................

Enter first letter of show, insert, remove, update, q to quit: i

Enter value to insert: Name: name11

Sequence Number: 1097

Salary: 66666

Enter first letter of show, insert, remove, update, q to quit: s

heapArray: [name6|1099|48999.00] [name11|1097|66666.00] [name5|1098|81123.00] [n

ame2|1078|82221.00] [name4|1088|91110.00] [name3|1065|45691.00] [name7|1054|6722

3.00] [name1|1048|65435.00] [name8|1062|71112.00] [name10|1085|71000.00]

................................................................

[name6|1099|48999.00]

[name11|1097|66666.00] [name5|1098|81123.00]

[name2|1078|82221.00] [name4|1088|91110.00] [name3|1065|45691.00]

[name7|1054|67223.00]

[name1|1048|65435.00] [name8|1062|71112.00] [name10|1085|71000.00]