using comparable in java for Bubble up in MaxHeap

Question

I am trying to insert in a maxHeap in java and then bubble up the object. This is what I have done, I am not sure how I should approach the bubble up method.

I do understand the algorithm behind bubble up, which is as follows:

1. get parent node
2. see if L_childNode is less than parent Node. If Yes, then swap parent with L_child.
3. see if R_childNode is less than parent Node. If Yes, then swap parent with L_child.

Please point out what am I doing wrong?

private int getLeftChild(int n){
        return x*2+1;
    }

    private int getRightChild(int n){
        return x*2+2;
    }

    public void insert (E item) {
        //Integer pos_lastEl= new Integer (heapArray.lastElement());
        heapArray.add(item);


        bubbleUp(item);
    }

    //To use to reheap up when item inserted at end of heap (complete tree)
    private void bubbleUp(E x){
        int place = heapArray.size()-1;
        int parent=(place-1)/2;
        if ((parent>=0) && (parent.compareTo(heapArray.get(getLeftChild))<0)){
            swap(place,parent);
        }else ((parent>=0 && (parent.compareTo(heapArray.get(getRightChild))<0))){
            swap(place,parent);
        }
    }

    //swaps two objects at index i and j
    private void swap(int i, int j){
        int max=heapArray.size();
        if(i>=0 && i<max && j>=0 && j<max){
            E temp=heapArray.get(i);
            //put J item in I
            heapArray.set(i,heapArray.get(j));
            heapArray.set(j,temp);
        }
    }

Answer 1

Your major problem is using if instead of while to bubble up the newly added element to the proper position.

And there are also some other issues in your code, sorry I had to do some refactoring to make it clean enough:

public class MaxHeapTest<E extends Comparable<E>> {
    List<E> heapArray = new ArrayList<>();

    public static void main(String... args) {
        int N = 13;
        MaxHeapTest<Integer> maxHeap = new MaxHeapTest();
        for (int i = 0; i < N; ++i) { // ascending;
            maxHeap.insert(i);
        }

        while (!maxHeap.isEmpty()) { // descending now;
            System.out.print(maxHeap.delMax() + " ");
        }
    }

    public E delMax() {
        E e = heapArray.get(0);
        swap(0, heapArray.size() - 1);
        heapArray.remove(heapArray.size() - 1);
        sinkDown(0);
        return e;
    }

    public void insert(E item) {
        heapArray.add(item);
        bubbleUp(item);
    }

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

    private void bubbleUp(E x) {
        int k = heapArray.indexOf(x);
        int j = (k - 1) / 2;
        while (j >= 0) {
            if (heapArray.get(j).compareTo(heapArray.get(k)) < 0) {
                swap(k, j);
                k = j;
                j = (j - 1) / 2;
            } else break;
        }
    }

    private void sinkDown(int k) {
        int j = 2 * k + 1;
        while (j < heapArray.size()) {
            if (j < heapArray.size() - 1 && heapArray.get(j).compareTo(heapArray.get(j + 1)) < 0) j++;
            if (heapArray.get(k).compareTo(heapArray.get(j)) < 0) {
                swap(k, j);
                k = j;
                j = 2 * j + 1;
            } else break;
        }
    }

    private void swap(int i, int j) {
        E temp = heapArray.get(i);
        heapArray.set(i, heapArray.get(j));
        heapArray.set(j, temp);
    }
}

After the maxHeap, we can easily output the descending numbers as:

12 11 10 9 8 7 6 5 4 3 2 1 0