[SOLVED] Help with Min Heap Implementation (with an array)
I'm trying to implement a Min Heap in Java, but I'm having issues with inserting and removing elements (inserting at the end, removing the root as min). It seems to work for the most part (I use a program to visually display the heap and have been printing out the new roots when min has been removed, things like that).
My problem is, for some reason the root won't switch with a new item when a new item is added, but I can't figure out why at all. Also, it seems this is only the problem when there are a lot of duplicates, the heap doesn't seem completely capable of staying in order (the parent is smaller than the children). For the most part, it does. Only occasionally it doesn't, and to me it seems random.
This is done with generics, and basically following most algorithms. Everything else I know for a fact works, it's definitely a problem with these two methods.
PHP Code:
public void insert(T e) {
if (size == capacity)
increaseSize(); //this works fine
last = curr; //keeping track of the last index, for heapifying down/bubbling down when removing min
int parent = curr/2;
size++; //we added an element, so the size of our data set is larger
heap[curr] = e; //put value at end of array
//bubble up
int temp = curr;
while (temp > 1 && ((Comparable<T>) heap[temp]).compareTo(heap[parent]) < 0) { //if current element is less than the parent
//integer division
parent = temp/2;
swap(temp, parent); //the swapping method should be correct, but I included it for clarification
temp = parent; //just moves the index value to follow the element we added as it is bubbled up
}
curr++; //next element to be added will be after this one
}
public void swap(int a, int b){
T temp = heap[a];
heap[a] = heap[b];
heap[b] = temp;
}
public T removeMin() {
//root is always min
T min = heap[1];
//keep sure array not empty, or else size will go negative
if (size > 0)
size--;
//put last element as root
heap[1] = heap[last];
heap[last] = null;
//keep sure array not empty, or else last will not be an index
if (last > 0)
last--;
//set for starting at root
int right = 3;
int left = 2;
int curr = 1;
int smaller = 0;
//fix heap, heapify down
while(left < size && right < size){ //we are in array bounds
if (heap[left] != null && heap[right] != null){ //so no null pointer exceptions
if (((Comparable<T>)heap[left]).compareTo(heap[right]) < 0) //left is smaller
smaller = left;
else if (((Comparable<T>)heap[left]).compareTo(heap[right]) > 0) //right is smaller
smaller = right;
else //they are equal
smaller = left;
}
if (heap[left] == null || heap[right] == null)//one child is null
{
if (heap[left] == null && heap[right] == null)//both null, stop
break;
if (heap[left] == null)//right is not null
smaller = right;
else //left is not null
smaller = left;
}
if (((Comparable<T>)heap[curr]).compareTo(heap[smaller]) > 0)//compare smaller or only child
{
swap(curr,smaller); //swap with child
curr = smaller; //so loop can check new children for new placement
}
else //if in order, stop
break;
right = 2*curr + 1; //set new children
left = 2*curr;
}
return min; //return root
}
Any variables not declared in the methods are global, and I know a couple of things are probably redundant, like the whole current/last/temp situation in add, so I'm sorry about that. I tried to make all names self explanatory and explain all the checks I did in removeMin. Any help would be insanely appreciated, I've gotten as far as I can looking things up and debugging. I think I'm just fundamentally missing something here.
Re: Help with Min Heap Implementation (with an array)
Can you make a small complete program for testing that compiles, executes and shows the problem?
Re: Help with Min Heap Implementation (with an array)
I have one, but the problem is that the complete program is decently complex and uses an AVL tree, corpus, and a special class for the comparisons for the data I'm inputting.
I can make a shorter, simpler one, but it'll take me a little bit. Should I include methods for the graphical output, or would that unnecessary? You have to use a separate program to even see that is the thing.
Re: Help with Min Heap Implementation (with an array)
The minimum that shows the problem. No GUI would be needed. Hardcode as much as possible so as not to require user input.
Re: Help with Min Heap Implementation (with an array)
Quote:
Originally Posted by
arsparfven
I have one, but the problem is that the complete program is decently complex and uses an AVL tree, corpus, and a special class for the comparisons for the data I'm inputting.
I can make a shorter, simpler one, but it'll take me a little bit. Should I include methods for the graphical output, or would that unnecessary? You have to use a separate program to even see that is the thing.
Actually, if it's more helpful, I could attach all the classes I am using (in a zip or rar file, of course). They have a pretty nice output set up that couldn't be achieved really without a lot of the classes and methods. But I know that the rest of them are correct, so that might be nice.
Re: Help with Min Heap Implementation (with an array)
Since I don't have a simple program for output yet, this is an example of output. This is me removing a minimum element (the root), and then removing the next minimal element (after the program replaces the root and heapifies down).
I'm "comparing" them by how many times each character shows up in a text file. 0x0A is new line, things like that are supposed to be counted. As you can see, 0x0A was kept as the root, when clearly it has more than 1 occurance. And for the most part after that things are in order, but around 1/2/3/4 there are some mess ups. I can't think of why that would happen.
:
Removing elements in sorted order:
0x0A [45]
' [1]
1 [1]
E [1]
F [1]
2 [1]
( [1]
7 [1]
K [1]
8 [1]
x [1]
N [1]
G [2]
\" [3]
) [1]
; [1]
S [1]
? [1]
Y [1]
@ [1]
: [2]
W [2]
` [2]
p [3]
O [4]
R [4]
- [4]
D [2]
L [4]
H [4]
B [5]
j [5]
. [6]
J [6]
v [6]
C [7]
T [9]
k [10]
f [11]
A [11]
! [11]
c [16]
y [18]
, [19]
g [23]
u [27]
m [28]
w [28]
b [32]
d [34]
l [36]
i [42]
n [44]
0x0D [45]
s [45]
r [46]
a [60]
h [63]
o [66]
t [67]
e [93]
0x20 [186]
1 Attachment(s)
Re: Help with Min Heap Implementation (with an array)
For the whole program, the zip is attached. It has everything you need, and maybe some extra files because of how eclipse works. All the input is in testFile, a text file in this folder. Currently it has my most recent test text. The output being printed currently shows what is being added and the number of times it shows up in the text file (or count), and then displays the data in essentially what should be in ascending order based on number of views. It does this by removing the min element of the heap until the heap is empty.
If anyone already has graphviz, all you need to do to see the output in a tree like form (graphically, if you will) is open the "outputHeap" file in graphviz (xdot on most linux platforms and gvedit on windows are the running files from graphviz to display .dot)
Re: Help with Min Heap Implementation (with an array)
Sorry if I'm posting too much, I'm just trying to get as much information out as I can.
Using this as a main to test the heap:
PHP Code:
MinHeap<Integer> heap = new MinHeap<Integer>();
for(int i = 0; i < 10; i++){
heap.insert(i);
}
heap.insert(3);
heap.insert(3);
heap.insert(2);
Integer min = heap.removeMin();
do{
System.out.println(min);
min = heap.removeMin();
}while(min != null);
The heap works perfectly fine. The output is
0
1
2
2
3
3
3
4
5
6
7
8
9
ALL of the Heap class is (sans graphical methods)
PHP Code:
public class MinHeap<T> {
public T[] heap= null;
private int last = 1;
private int capacity = 0; //capacity of the heap array
private int size = 1;
private int curr = 1;
MinHeap(){
capacity=2;
heap = (T[]) (new Object[capacity]);
}
public void insert(T e) {
if (size == capacity)
increaseSize();
last = curr;
int parent = curr/2;
size++;
heap[curr] = e;
//bubble up
int temp = curr;
while (temp > 1 && ((Comparable<T>) heap[temp]).compareTo(heap[parent]) < 0) {
//integer division
parent = temp/2;
swap(temp, parent);
temp = parent;
}
curr++;
}
public void increaseSize(){
capacity=2*capacity;
T[] next = (T[]) (new Object[capacity]);
for (int i = 0; i < size; i++){
next[i] = heap[i];
}
heap = next;
}
public void swap(int a, int b){
T temp = heap[a];
heap[a] = heap[b];
heap[b] = temp;
}
int size() {
return size;
}
public T removeMin() {
//root is always min
T min = heap[1];
//keep sure array not empty
if (size > 0)
size--;
//put last element as root
heap[1] = heap[last];
heap[last] = null;
//keep sure array not empty
if (last > 0)
last--;
//set for starting at root
int right = 3;
int left = 2;
int curr = 1;
int smaller = 0;
//fix heap, heapify down
while(left < size && right < size){ //we are in array bounds
if (heap[left] != null && heap[right] != null){ //so no null pointer exceptions
if (((Comparable<T>)heap[left]).compareTo(heap[right]) < 0) //left is smaller
smaller = left;
else if (((Comparable<T>)heap[left]).compareTo(heap[right]) > 0) //right is smaller
smaller = right;
else //they are equal
smaller = left;
}
if (heap[left] == null || heap[right] == null)//one child is null
{
if (heap[left] == null && heap[right] == null)//both null, stop
break;
if (heap[left] == null)//right is not null
smaller = right;
else //left is not null
smaller = left;
}
if (((Comparable<T>)heap[curr]).compareTo(heap[smaller]) > 0)//compare smaller or only child
{
swap(curr,smaller); //swap with child
curr = smaller; //so loop can check new children for new placement
}
else //if in order, stop
break;
right = 2*curr + 1; //set new children
left = 2*curr;
}
return min; //return root
}
}
Once I change the input to say, 20 Integers, this is my output
0
1
2
3
3
4
2
3
5
6
7
8
9
10
11
12
13
14
15
16
17
19
18
Which is incorrect. There is a 2 and 3 after the 4. Yet for the most part it is in order.
Re: Help with Min Heap Implementation (with an array)
I found something that was wrong, in my insert method. While bubbling up, in the while loop, I was modifying the parent in the wrong place. The lines inside the while loop should go
PHP Code:
swap(temp, parent);
temp = parent;
parent = temp/2;
Otherwise, the statements I was using to check when the loop should run would be based off of the wrong parent.
My insert method is now fully functional, however something still appears to be wrong with my remove min. I'm still looking at that and don't have sample output yet, but for the most part the program is probably about 40% more functional than it was before.
Re: Help with Min Heap Implementation (with an array)
Quote:
Originally Posted by
arsparfven
I found something that was wrong, in my insert method. While bubbling up, in the while loop, I was modifying the parent in the wrong place. The lines inside the while loop should go
PHP Code:
swap(temp, parent);
temp = parent;
parent = temp/2;
Otherwise, the statements I was using to check when the loop should run would be based off of the wrong parent.
My insert method is now fully functional, however something still appears to be wrong with my remove min. I'm still looking at that and don't have sample output yet, but for the most part the program is probably about 40% more functional than it was before.
I believe my problem now is just that the duplicates aren't ordered in any way as a subset on their own (like, if they are duplicates because their number count is the same in a text file, they aren't order in alphabetical order after that). This isn't actually a problem, just some extra coding that I forgot to implement.
Thank you very much Norm, for at least attempting to look at my problem and asking me about it. Thankfully I figured it out, but it was still quite appreciated.
Re: Help with Min Heap Implementation (with an array)
Glad you found the problem. I was being what we used to call a "cardboard" programmer. In the process of explaining a problem the programmer with the problem often uses a different part of his brain and looks at the problem from a different point of view to talk about the problem and in doing that finds the solution to problem long before he has explained enough for the "cardboard" programmer to understand it. So I just sit here like a piece of cardboard.
