public class MyPriorityQueue{
private static class jobAd{
public float salary;
public float dist;
public float score;
public jobAd(){
}
public jobAd(float s, float d){
salary = s;
dist = d;
score = s + 3 * (30 - d);
}
}
public class MyMaxHeap{
private jobAd[] theHeap;
private int size;
private int capacity;
private static final int initial_cap = 5;
public MyMaxHeap(){
size = 0;
capacity = initial_cap;
theHeap = new jobAd[capacity];
}
public MyMaxHeap(jobAd[] arr, int n){
theHeap = arr;
size = n;
buildHeap();
}
public int lc(int index){
return (2*index) + 1;
}
public int rc(int index){
return (2*index) + 2;
}
public int parent(int index){
if (index % 2 == 0) {
return (index - 2)/2;
}
else{
return (index - 1)/2;
}
}
public int size(){
return size;
}
public int compare(int i, int j){
if(theHeap[i].score > theHeap[j].score){
return 1;
}
if(theHeap[i].score == theHeap[j].score){
return 0;
}
else{
return -1;
}
}
public boolean add(jobAd job){
if(size == capacity){
jobAd[] newJobAd = new jobAd[2 * size];
System.arraycopy(newJobAd,0,theHeap,0,capacity);
theHeap = newJobAd;
}
theHeap[size] = job;
size++;
if(size > 1){
shiftDown(parent(size - 1));
}
return true;
}
private boolean rectify(int index){
if(lc(index) < size){
// if there is no right child or the left child is greater than the right child
if(rc(index) >= size || compare(lc(index), rc(index)) > 0){
// if the left child is greater than the index
if(compare(lc(index), index) > 0){
swap(lc(index), index);
return true;
}
}
// if the right child is greater than index
else if(compare(rc(index), index) > 0){
swap(rc(index), index);
return true;
}
}
return false;
}
public jobAd removeMax(){
theHeap[0] = theHeap[--size];
for(int i = 0; i < size - 1; i++){
rectify(i);
}
return theHeap[0];
}
public void buildHeap(){
int temp = size;
size = 0;
for(int i = 0; i < temp; i++){
add(theHeap[i]);
}
}
public void shiftDown(int index){
if(rectify(index) && index != 0){
shiftDown(parent(index));
}
}
public void shiftUp(int index){
if(index >= 0 && index < size){
if(compare(index, parent(index)) > 0){
swap(parent(index), index);
shiftUp(parent(index));
}
}
}
public void swap(int i, int j){
jobAd temp = new jobAd();
temp = theHeap[i];
theHeap[i] = theHeap[j];
theHeap[i] = temp;
}
public void showList(){
int i;
for(i = 0; i < size; i++){
System.out.println("List: " + theHeap[i].score);
}
}
/*
public static void main(String[] args){
MyMaxHeap myQ = new MyMaxHeap();
jobAd job1 = new jobAd((float) 1.1, (float) 13.01);
myQ.add(job1);
jobAd job2 = new jobAd((float) 2.1, (float) 13.01);
myQ.add(job2);
jobAd job3 = new jobAd((float) 3.1, (float) 13.01);
myQ.add(job3);
jobAd job4 = new jobAd((float) 4.1, (float) 13.01);
myQ.add(job4);
jobAd job5 = new jobAd((float) 5.1, (float) 13.01);
myQ.add(job5);
myQ.showList();
//s + 3 * (30 - d)
System.out.println(myQ.size());
}*/
}
private MyMaxHeap theQueue;
private int size;
public MyPriorityQueue(){
theQueue = new MyMaxHeap();
}
public MyPriorityQueue(jobAd[] arr, int n){
theQueue = new MyMaxHeap(arr, n);
}
public int size(){
return size;
}
public boolean isEmpty(){
if(theQueue == null){
return true;
}
return false;
}
public boolean offer(jobAd jA){
theQueue.add(jA);
return true;
}
public jobAd remove(){
if(isEmpty()){
return null;
}
else{
theQueue.removeMax();
return theQueue.removeMax();
}
}
public jobAd peek(){
if(isEmpty()){
return null;
}
else{
return theQueue[0]; //return queue item at index 0, which is the max
}
}
public void showList(){
int i;
for(i = 0; i < size; i++){
System.out.println("List: " + theQueue[i]); //print out element at index i, which increments to print out rest of list
}
}
public static void main(String[] args){
MyPriorityQueue myQ = new MyPriorityQueue();
jobAd job1 = new jobAd((float) 1.1, (float) 13.01);
myQ.offer(job1);
jobAd job2 = new jobAd((float) 2.1, (float) 13.01);
myQ.offer(job2);
jobAd job3 = new jobAd((float) 3.1, (float) 13.01);
myQ.offer(job3);
jobAd job4 = new jobAd((float) 4.1, (float) 13.01);
myQ.offer(job4);
jobAd job5 = new jobAd((float) 5.1, (float) 13.01);
myQ.offer(job5);
myQ.showList();
//s + 3 * (30 - d)
System.out.println(myQ.size());
}
}