Krdytkyu

There is a Min-Heap implementation in Java. BubbleUp() and BubbleDown() could have been coded using recursion but I prefer without recursion. Would there be a major difference if had used recursion?

package heap;



import interfaces.queue.PriorityQueue;

import java.util.Arrays;

import java.util.stream.Collectors;



public class Heap<T extends Comparable<T>> implements 

PriorityQueue<T>

{

    private T elements;

    private int size;

    private int capacity;



    public Heap()

    {

        this(500);

    }



    public Heap(int capacity)

    {

        this.capacity = capacity;

        size = 0;

        elements = (T) new Comparable[this.capacity];

    }



    public int size()

    {

        return size;

    }



    public boolean isEmpty()

    {

        return size() == 0;

    }



    @Override

    public void add(T data) throws Exception

    {

        if(size() >= capacity) throw new Exception("Heap is full");

        elements[size++] = data;

        bubbleUp();

    }



    private void bubbleUp()

    {

        int child = size() - 1;

        int parent = (child-1)/2;



        while(parent >= 0 && elements[child].compareTo(elements[parent]) < 0)

        {

            swap(child, parent);

            child = parent;

            parent = (child-1)/2;

        }

    }



    @Override

    public T removeMin() throws Exception

    {

        if(isEmpty()) throw new Exception("Empty heap");

        T root = elements[0];

        swap(size()-1, 0);

        elements[size()-1] = null;

        size--;

        bubbleDown();

        return root;

    }



    private void bubbleDown()

    {

        int parent = 0;

        int leftChild = 2*parent + 1;

        int rightChild = 2*parent + 2;



        int choice = compareAndPick(leftChild, rightChild);



        while(choice != -1)

        {

            swap(choice, parent);

            parent = choice;

            choice = compareAndPick(2*choice+1, 2*choice+2);

        }

    }



    private int compareAndPick(int leftChild, int rightChild)

    {

        if(leftChild >= capacity || elements[leftChild] == null) return -1;

       if((elements[leftChild].compareTo(elements[rightChild]) <= 0)|| (elements[rightChild] == null))

            return leftChild;

        return rightChild;

    }



    private void swap(int child, int parent)

    {

        T t = elements[child];

        elements[child] = elements[parent];

        elements[parent] = t;

    }



    @Override

    public String toString()

    {

         return Arrays.stream(elements)

                 .filter(element -> element != null)

                 .collect(Collectors.toList()).toString();

    }

}

I do not endorse recursion when a clean and simple iterative iterative solution is readily available. You did the right thing.

The only problem I have is with compareAndPick implementation. First, rightChild is not tested against capacity, and may cause an out-of-bounds access. Second, testing elements[rightChild] against null looks too late (how does compareTo(null) behave?). Finally, there is really no need to test both an index against capacity and an object against nullness: index < size guarantees both.

You may consider renaming compareAndPick to selectSmallestChild (and choice to child).

Also, I recommend to leave the children computation to compareAndPick, and have a terser version of bubbleDown loop:

    while ((child = selectSmallestChild(parent)) != -1) {

        swap(child, parent);

        parent = child;

    }