Re: PriorityQ and MaxHeap
Quote:
Originally Posted by
lahegemon
Okay, so I have an assign,ent to write a priority queue that implements a max heap. I've only just started the program and this is what I have for my MyMaxHeap class:
Code :
public class MyMaxHeap{
private static class jobAd{
public float salary;
public float dist;
public float score;
public jobAd(float s, float d){
s = salary;
d = dist;
score = s + 3 * (30 - d);
}
}
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;
n = size;
}
public int size(){
return size;
}
public boolean add(jobAd job){
if ((size >= capacity) || (job == null)){
return false;
}
return true;
}
public static void main(String[] args){
MyMaxHeap myHeap = new MyMaxHeap();
System.out.println(myHeap.size());
}
}
My problem here is that I don't understand how to add/insert a new new element to the list. I've tried a few things and they ended with several errors. Also, this heap is to be sorted by score. I don't know how to compare the two scores without using theHeap[index].score.compareTo(theHeap[index2] which also gives several errors. Please help!! I just need to know how to start this and then I'll work on it on my own. Thank you. :)
Quote:
I've tried a few things and they ended with several errors.
Such as.......?
n = size;
Don't you mean
size = n;
?
I don't see where size is set otherwise.
What is the capacity value set to in
public MyMaxHeap(jobAd[] arr, int n){
theHeap = arr;
n = size;
}
?
When is the jobAd array ever filled?
Re: PriorityQ and MaxHeap
Do you understand the concept of Heap? If yes, start implementing and come back here after you get errors or you get stuck somewhere. You didn't even try anything except creating a self defined object. Naming an object heap will surely not make it working like a heap. You must take the concept of Heap, then think and start implementing.
Regards
Re: PriorityQ and MaxHeap
Code :
public class MyMaxHeap{
private class jobAd{
public float salary;
public float dist;
public float score;
public jobAd(float s, float d){
s = salary;
d = dist;
score = s + 3 * (30 - d);
}
}
private jobAd[] theHeap;
private int size;
private int capacity;
public MyMaxHeap(){
size=0;
capacity = 5;
theHeap = new jobAd[capacity];
}
public MyMaxHeap(jobAd[] arr, int n){
theHeap=arr;
size=n;
buildHeap();
}
public int getSize(){
return size;
}
public boolean add(jobAd job){
int index;
if((size>=theHeap.length)||(job==null)){
return false;
}
theHeap[size++]=job;
index=shiftUp(size-1);
return true;
}
public jobAd removeMax(){
if(size <= 0){
return null;
}
swap(0,--size);
shiftDown(0);
return theHeap[size];
}
private void shiftDown(int index){
int leftChild;
if((index>=0)&&(index<(size/2))){
leftChild=2*index+1;
if(((leftChild+1)<size)&&((Comparable)theHeap[leftChild]).compareTo(theHeap[leftChild+1])<0){
leftChild++;
}
if(((Comparable)theHeap[index]).compareTo(theHeap[leftChild])<0){
swap(index,leftChild);
shiftDown(leftChild);
}
}
}
private int shiftUp(int index){
int parent;
if((index>0)&&(index<size)){
parent=(index-1)/2;
if(((Comparable)theHeap[index]).compareTo(theHeap[parent])>0){
swap(parent,index);
return shiftUp(parent);
}
}
return index;
}
private void swap(int i, int j)
{
if((i>=0)||(j>=0)||(i<theHeap.length)||(j<theHeap.length)){
jobAd temp = theHeap[i];
theHeap[i]=theHeap[j];
theHeap[j]=temp;
}
}
private void buildHeap()
{
int i;
for(i=(size/2-1);i>=0;i--)
{
shiftDown(i);
}
}
public void showList(){
for(int i = 0; i < size; i++){
System.out.println("List: " + theHeap[i]);
}
}
public static void main(String[] args){
MyMaxHeap myHeap = new MyMaxHeap();
System.out.println(myHeap.size);
}
}
Okay, so that's my code for my max heap so far, guys. It compiles without errors but notice that I have a jobAd class? I need my heap to be sorted by the value of score and I'm not sure if I'm doing that. I'd appreciate any help available thanks.
Re: PriorityQ and MaxHeap
Code :
public class MyMaxHeap{
private class jobAd{
public float salary;
public float dist;
public float score;
public jobAd(float s, float d){
s = salary;
d = dist;
score = s + 3 * (30 - d);
}
}
private jobAd[] theHeap;
private int size;
private int capacity;
public MyMaxHeap(){
size=0;
capacity = 5;
theHeap = new jobAd[capacity];
}
public MyMaxHeap(jobAd[] arr, int n){
theHeap=arr;
size=n;
buildHeap();
}
public int getSize(){
return size;
}
public boolean add(jobAd job){
int index;
if((size>=theHeap.length)||(job==null)){
return false;
}
theHeap[size++]=job;
index=shiftUp(size-1);
return true;
}
public jobAd removeMax(){
if(size <= 0){
return null;
}
swap(0,--size);
shiftDown(0);
return theHeap[size];
}
private void shiftDown(int index){
int leftChild;
if((index>=0)&&(index<(size/2))){
leftChild=2*index+1;
if(((leftChild+1)<size)&&((Comparable)theHeap[leftChild]).compareTo(theHeap[leftChild+1])<0){
leftChild++;
}
if(((Comparable)theHeap[index]).compareTo(theHeap[leftChild])<0){
swap(index,leftChild);
shiftDown(leftChild);
}
}
}
private int shiftUp(int index){
int parent;
if((index>0)&&(index<size)){
parent=(index-1)/2;
if(((Comparable)theHeap[index]).compareTo(theHeap[parent])>0){
swap(parent,index);
return shiftUp(parent);
}
}
return index;
}
private void swap(int i, int j)
{
if((i>=0)||(j>=0)||(i<theHeap.length)||(j<theHeap.length)){
jobAd temp = theHeap[i];
theHeap[i]=theHeap[j];
theHeap[j]=temp;
}
}
private void buildHeap()
{
int i;
for(i=(size/2-1);i>=0;i--)
{
shiftDown(i);
}
}
public void showList(){
for(int i = 0; i < size; i++){
System.out.println("List: " + theHeap[i]);
}
}
public static void main(String[] args){
MyMaxHeap myHeap = new MyMaxHeap();
System.out.println(myHeap.size);
}
}
Okay, that's my code. It compiles without error. However, I am confused about one thing and I was hoping you could clarify it for me. This is supposed to be a MaxHeap that sorts by score. How do I ensure that it is sorting by the value of score (in jobAd class) and not salary or dist (distance) ? Thanks!
Re: PriorityQ and MaxHeap
capacity is set in a separate constructor also, look at my reply below. that's my current program but...well, my questions are in the same post. Thanks
Re: PriorityQ and MaxHeap
You manually define the comparison method. The way I prefer to do it is with a comparator object, but that may be too generic for what you're trying to accomplish here.
It's probably fine for you to "hard code" what to compare in your MyMaxHeap class.
Re: PriorityQ and MaxHeap
Precisely what I was thinking. Couldn't I just replace my comparisons for some of my theHeap[index] comparisons with theHeap[index].score comparisons? But then I would ave to write a separate function that returns score, right? Inside of my jobAd class? and Thanks for getting back to me so quickly.
