I am trying to practice coding some data structures in Java, and have a problem with Binary Heap, I'd be very grateful if you could help me.
First I've made a class for objects that will be stored in the heap.
public class Person {
private String name;
private String surname;
private int age;
public Person(String name, String surname, int age) {
this.name = name;
this.surname = surname;
this.age = age;
}
public void setName(String n) {
name = n;
}
public void setSurname(String n) {
surname = n;
}
public void setAge(int a) {
age = a;
}
public String getName() {
return name;
}
public String getSurname() {
return surname;
}
public int getAge() {
return age;
}
}
Then I've made a class for heap nodes in which Person objects will be held as well as node priorities.
public class BinNode {
private Person element;
private int priority;
BinNode(Person element, int priority) {
this.element = element;
this.priority = priority;
}
public boolean isEmpty() {
if (element == null)
return true;
else
return false;
}
public Person getElement() {
return element;
}
public int getPriority() {
return priority;
}
@Override
public String toString() {
return "Data: " + element.getName() + " " + element.getSurname() +
". Age: " + element.getAge() + "." + " Priority: " + priority + ".";
}
}
And finally I've made a class for binary heap.
public class BinHeap {
public BinNode[] tab;
public int counter;
BinHeap(Person root, int priority) {
counter = 1;
tab = new BinNode[10];
BinNode rt = new BinNode(root, priority);
tab[counter++] = rt;
}
public void upheap(int i) {
while((i > 1) && (tab[i].getPriority() < tab[i-1].getPriority())) {
BinNode temp = tab[i-1];
tab[i-1] = tab[i];
tab[i] = temp;
i--;
}
}
//error somewhere here
public void downheap(int i) {
int l = 2 * i;
int r = 2 * i + 1;
while (r < counter-1 && l < counter) {
l = 2 * i;
r = 2 * i + 1;
if(tab[l].getPriority() < tab[r].getPriority()) {
BinNode temp = tab[i];
tab[i] = tab[l];
tab[l] = temp;
i = l;
} else if (tab[l].getPriority() >= tab[r].getPriority()) {
BinNode temp = tab[i];
tab[i] = tab[r];
tab[r] = temp;
i = r;
}
}
}
public void insert(Person p, int priority) {
BinNode node = new BinNode(p, priority);
tab[counter++] = node;
upheap(counter-1);
}
public BinNode findMin() {
return tab[1];
}
//or here
public void delMin() {
tab[1] = tab[counter];
tab[counter--] = null;
downheap(1);
}
public void showTree() {
for (int i = 1; i < tab.length; i++) {
if(tab[i] != null) {
System.out.println(i + " - " + tab[i].toString());
}
}
}
}
This Main class:
public class Main {
public static void main(String[] args) {
Person mary = new Person("Mary", "Green", 20);
Person mark = new Person("Mark", "Yellow", 60);
Person john = new Person("John", "Dark", 12);
Person adam = new Person("Adam", "Bright", 30);
Person martha = new Person("Martha", "King", 33);
Person greg = new Person("Greg", "Pawn", 1);
BinHeap heap = new BinHeap(mary, 2);
heap.showTree();
System.out.println();
heap.insert(mark, 4);
heap.insert(john, 12);
heap.showTree();
System.out.println();
heap.insert(adam, 1);
heap.showTree();
System.out.println();
System.out.println("root: " + heap.findMin().toString());
System.out.println();
heap.insert(martha, 5);
heap.insert(greg, 15);
heap.showTree();
System.out.println();
heap.delMin();
heap.showTree();
}
}
Produces the following output:
1 - Data: Mary Green. Age: 20. Priority: 2.
1 - Data: Mary Green. Age: 20. Priority: 2.
2 - Data: Mark Yellow. Age: 60. Priority: 4.
3 - Data: John Dark. Age: 12. Priority: 12.
1 - Data: Adam Bright. Age: 30. Priority: 1.
2 - Data: Mary Green. Age: 20. Priority: 2.
3 - Data: Mark Yellow. Age: 60. Priority: 4.
4 - Data: John Dark. Age: 12. Priority: 12.
root: Data: Adam Bright. Age: 30. Priority: 1.
1 - Data: Adam Bright. Age: 30. Priority: 1.
2 - Data: Mary Green. Age: 20. Priority: 2.
3 - Data: Mark Yellow. Age: 60. Priority: 4.
4 - Data: Martha King. Age: 33. Priority: 5.
5 - Data: John Dark. Age: 12. Priority: 12.
6 - Data: Greg Pawn. Age: 1. Priority: 15.
1 - Data: Mary Green. Age: 20. Priority: 2.
2 - Data: Martha King. Age: 33. Priority: 5.
3 - Data: Mark Yellow. Age: 60. Priority: 4.
5 - Data: John Dark. Age: 12. Priority: 12.
6 - Data: Greg Pawn. Age: 1. Priority: 15.
As you can see, as long as we are putting new nodes into the heap it all works good. However when we want to delete the root node, downheap method (or perhaps delMin method) does not work properly.
As you can see the node "Martha King" with priority of 5 is higher in the heap than "Mark Yellow" node with priority of 4.
EDIT: It seems that I didn't understand how the binary heap behaves when implemented as an array. So the above sentence in bold is not true. The original output is wrong because the heap lost its completeness property, since array[4] is empty.
I just can't figure that one out. Could you please help me? Thank you. Also some general comments about coding style, etc. would be appreciated. This is my first post on stack overflow so sorry if I've messed something up.
