Thread: 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.

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.

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]

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)

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.

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.

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.