Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 11 of 11

Thread: Help with Min Heap Implementation (with an array)

  1. #1
    Junior Member
    Join Date
    Apr 2012
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Exclamation [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 && ((Comparable<T>) heap[temp]).compareTo(heap[parent]) < 0) { //if current element is less than the parent
                //integer division
                
    parent temp/2;
                
    swap(tempparent); //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 aint 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.
    Last edited by arsparfven; April 26th, 2012 at 08:31 PM. Reason: Was solved, wanted to change the title to reflect this


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,350
    Thanks
    49
    Thanked 2,204 Times in 2,177 Posts

    Default 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?
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Apr 2012
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,350
    Thanks
    49
    Thanked 2,204 Times in 2,177 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Apr 2012
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help with Min Heap Implementation (with an array)

    Quote Originally Posted by arsparfven View Post
    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.

  6. #6
    Junior Member
    Join Date
    Apr 2012
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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]

  7. #7
    Junior Member
    Join Date
    Apr 2012
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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)
    Attached Files Attached Files

  8. #8
    Junior Member
    Join Date
    Apr 2012
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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<Integerheap = new MinHeap<Integer>();
            for(
    int i 010i++){
                
    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[] heapnull;
        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 && ((Comparable<T>) heap[temp]).compareTo(heap[parent]) < 0) {
                
    //integer division
                
    parent temp/2;
                
    swap(tempparent);
                
    temp parent;
            }
            
            
    curr++;
            
            
        }
        
        public 
    void increaseSize(){
            
    capacity=2*capacity;
            
    T[] next = (T[]) (new Object[capacity]);
            
            for (
    int i 0sizei++){
                
    next[i] = heap[i];
            }
            
            
    heap next;
        }
        
        public 
    void swap(int aint 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.

  9. #9
    Junior Member
    Join Date
    Apr 2012
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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(tempparent);
    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.

  10. #10
    Junior Member
    Join Date
    Apr 2012
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help with Min Heap Implementation (with an array)

    Quote Originally Posted by arsparfven View Post
    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(tempparent);
    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.

  11. #11
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,350
    Thanks
    49
    Thanked 2,204 Times in 2,177 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. heap size vs heap used
    By aueddonline in forum Java Theory & Questions
    Replies: 5
    Last Post: February 10th, 2012, 12:59 PM
  2. Heap Memory
    By vamsi in forum Java Theory & Questions
    Replies: 3
    Last Post: November 19th, 2011, 11:48 AM
  3. binary heap
    By dabdi in forum Collections and Generics
    Replies: 0
    Last Post: November 16th, 2011, 04:43 PM
  4. Implementation Stack Using Array
    By rainbow9 in forum Java Programming Tutorials
    Replies: 1
    Last Post: August 20th, 2011, 09:48 AM
  5. Implementing a 5-heap with an array
    By TBBucs in forum Algorithms & Recursion
    Replies: 0
    Last Post: April 12th, 2010, 10:56 PM

Tags for this Thread