Java Arraylist Heap Implementation

Question

I am trying to implement an insert() method for an arraylist-based heap implementation, but whenever I test the method inserting more than one integer where at least one of them is greater than ~4 the program takes forever to run. For example, stating heap.insert(1) and heap.insert(8) together in the main function will take forever to run. Here is my heap class:

import java.util.*;


public class Heap<E extends Comparable<E>> implements HeapAPI<E>
{
    /**
     * A complete tree stored in an array list representing this
     * binary heap
     */
    private ArrayList<E> tree;

    /**
     * Constructs an empty heap
     */
    public Heap()
    {
        tree = new ArrayList<E>();
    }

    public boolean isEmpty()
    {
       return tree.isEmpty();
    }

    public void insert(E obj)
    {
        tree.add(tree.size(), obj);
        siftUp(tree.size() - 1);
    }

    /**
     * siftUp from position k. The key or node value at position
     * may be greater that that of its parent at k/2.
     * @param k position in the heap arraylist
     */
    private void siftUp(int k)
    {
        E v = tree.get(k);
        while (v.compareTo(tree.get(k / 2)) == 1)
        {
            tree.add(k, tree.get(k / 2));
            k = k / 2;
        }
        tree.add(k, v);
    }

    public int size()
    {
       return tree.size();
    }
}

This is the pseudocode given to us by my professor that I modeled the insert() and siftUp() methods from:

The program works for small integers, for example, if I type heap.insert(1) a bunch of times in a row, but never finishes running if I change one of the numbers to a larger integer. No errors are thrown, as it doesn't finish executing when I try to run the program. I'm not sure what's going on. Any help is appreciated.

Tip: when you are not sure what your program is doing; learn how to use a debugger. Or at least: put in some print statements. Because that makes your code observable. And it is hard to guess what your code is doing, as your not giving all the code necessary to repro the issue. — GhostCat
– GhostCat, Commented Feb 13, 2017 at 18:31
You may want to use tree.set rather than tree.add to set the value of the ArrayList at a particular index. Otherwise, the new element is inserted into the position (shifting subsequent elements to the right), rather than replacing the existing value at that position. — David Choweller
– David Choweller, Commented Feb 13, 2017 at 18:32

Jim Mischel · Accepted Answer · 2017-02-13 20:48:41Z

Let's walk through your code here for a moment:

public void insert(E obj)
{
    tree.add(tree.size(), obj);
    siftUp(tree.size() - 1);
}

private void siftUp(int k)
{
    E v = tree.get(k);
    while (v.compareTo(tree.get(k / 2)) == 1)
    {
        tree.add(k, tree.get(k / 2));
        k = k / 2;
    }
    tree.add(k, v);
}

Now, you do the tree.insert(1), and everything works fine. Next you call tree.insert(0). Let's see what happens.

tree.add(tree.size(), obj) adds 0 as the next item in the array list. So you now have a list that contains [1, 0]
the code calls siftUp(1)
in siftUp, the first line gets element 1 from the array list. At this point, v = 1
at the while statement, the code compares the value, 1, to the value at tree[k/2]. Since k == 1, you're checking against the root node (i.e. tree[0]), which we know is equal to 1.
Because the new value is smaller than its parent, you copy the parent value to the new item's position. At this point, your array list contains [1, 1].
You divide your index, k, by 2, giving 0.
Now you're back to the while condition. k is equal to 0 and the value at tree[k] is 1, meaning that it's still greater than the value of v.
You're now in an infinite loop, continually comparing the value at index 0 with your temporary value.

The problem is that your loop has no definite ending condition.

One way to solve the problem is to end the loop if k == 0.

private void siftUp(int k)
{
    E v = tree.get(k);
    while (k > 0 && v.compareTo(tree.get(k / 2)) == 1)
    {
        tree.add(k, tree.get(k / 2));
        k = k / 2;
    }
    tree.add(k, v);
}

The next trouble you're going to have is that your calculation of the parent node is incorrect. If the root node of the heap is at index 0, then for a node at index ix, its left child is at (ix*2)+1, and the right child is at (ix*2)+2. The node's parent is at (ix-1)/2.

Consider the heap with three nodes:

        0
      1   2

Here the node numbers are the same as the array indexes.

If the root is at index 0, then the left node is at (2 * 0) + 1. The right node is at (2 * 0) + 2. The parent of 1 is (1-1)/2. And the parent of 2 is (2-1)/2. In your code, you parent calculation is k/2, which would give an incorrect value of 1 for the node labeled 2 in the heap above.

Collectives™ on Stack Overflow

Java Arraylist Heap Implementation

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related