Use Java Make Sure it Compiles //Please put comments Write a program that reads

Question

Use Java

Make Sure it Compiles

//Please put comments

Write a program that reads records containing an employee number and an hourly rate for several employees, and stores these in a heap, using employee number as a key. The program should then allow the user to insert or delete records, and finally use heap sort to sort the updates list so that the employee numbers are in ascending order, and to display this sorted list. You can use the algorithms from the text book. Example of an employee records will be: 7 10 2 11.50 5 9.50 48.50 11.50 10.50

Explanation / Answer

package heap;

class Employee{

int id;

double rate;

public Employee(int id,double rate) {

this.id=id;

this.rate=rate;

}

}

public class Heap {

Employee[] harr; // pointer to array of elements in heap

int capacity; // maximum possible size of min heap

int heap_size; // Current number of elements in min heap

Heap(int capacity){

this.capacity = capacity;

harr=new Employee[capacity];

heap_size=0;

}

  

int parent(int i) { return (i-1)/2; }

int left(int i) { return (2*i + 1); }

// to get index of right child of node at index i

int right(int i) { return (2*i + 2); }

// to heapify a subtree with root at given index

void heapify(int i ){

int l = left(i);

int r = right(i);

int smallest = i;

if (l < heap_size && compair(harr[l] , harr[i])<0)

smallest = l;

if (r < heap_size && compair(harr[r] , harr[smallest])<0)

smallest = r;

if (smallest != i)

{

swap(i, smallest);

heapify(smallest);

}

}

  

// to extract the root which is the minimum element

int extractMin(){

if (heap_size <= 0)

return Integer.MAX_VALUE;

if (heap_size == 1)

{

heap_size--;

return harr[0].id;

}

// Store the minimum value, and remove it from heap

int root = harr[0].id;

harr[0] = harr[heap_size-1];

heap_size--;

heapify(0);

return root;

}

// Decreases key value of key at index i to new_val

void decreaseKey(int i, int new_val){

harr[i].id = new_val;

while (i != 0 && compair(harr[parent(i)] , harr[i])>0)

{

swap(i, parent(i));

i = parent(i);

}

}

  

// Returns the minimum key (key at root) from min heap

Employee getMin() { return harr[0]; }

// Deletes a key stored at index i

void deleteKey(int i){

}

// Inserts a new key 'k'

void insertKey(Employee k){

if (heap_size == capacity)

{

System.out.println(" Overflow: Could not insertKey ");

return;

}

// First insert the new key at the end

heap_size++;

int i = heap_size - 1;

harr[i] = k;

// Fix the min heap property if it is violated

while (i != 0 && compair(harr[parent(i)] , harr[i])>0)

{

swap(i, parent(i));

i = parent(i);

}

}

public int compair(Employee e1, Employee e2){

if(e1.id<e2.id) return -1;

if(e1.id>e2.id) return 1;

return 0;

}

void swap(int x, int y)

{

Employee temp = harr[x];

harr[x] = harr[parent(x)];

harr[parent(x)] = temp;

}

public void print(){

for(int i=0; i<heap_size;i++){

System.out.println("ID:"+harr[i].id+" Rate:"+harr[i].rate);

}

}

void heapSort(int arr[], int n)

{

// Build heap (rearrange array)

for (int i = n / 2 - 1; i >= 0; i--)

heapify(i);

// One by one extract an element from heap

for (int i=n-1; i>=0; i--)

{

swap(arr[0], arr[i]);

heapify( 0);

}

}

public static void main(String[] args) {

Heap heap = new Heap(5);

heap.insertKey(new Employee(4,5));

heap.insertKey(new Employee(7,8));

heap.insertKey(new Employee(2,9.7));

heap.insertKey(new Employee(1,4));

heap.print();

}

}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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