1
\$\begingroup\$

This is my implementation of MinHeap in Java.

public class MinHeap {

        int[] heap;
        int pos;
        int size;


        public MinHeap(){
            this.size = 2;
            heap = new int[size];
            this.pos = 0;

        }

        private void minHeapify(int index){

            int child = index;
            int parent = child/2;

            while(heap[parent] > heap[child] && parent > 0){
                int temp = heap[parent];
                heap[parent] = heap[child];
                heap[child] = temp;

                child = parent;
                parent = child/2;
            }

        }
        public void add(int item){

            if(pos == heap.length) resize();
            heap[pos++] = item;

            minHeapify(pos-1);


        }
        public void delete(int item){
            boolean found = false;
            int start = 0;
            for(int i = 0; i< heap.length; i++){
                if(heap[i] == item){
                    found = true;
                    start = i;
                    break;
                }
            }
            if(found == false) throw new IllegalStateException("Item doesn't exist.");
            pos--;
            for(int i= start; i< pos; i++){
                heap[i]= heap[i+1];
            }
            for(int i=pos; i > 0; i--){
                minHeapify(i);
            }
        }

        public int min(){

            return heap[1];
        }

        private void resize(){

            size = size*2;
            int[] curr = new int[size];
            for(int i=0; i< heap.length; i++){
                curr[i] = heap[i];
            }
            heap = curr;

        }
    }

Invite comments and suggestions to improve.

\$\endgroup\$
2
\$\begingroup\$

There are numerous "microstyle" issues; for example:

  • superfluous blank lines
  • missing spaces before / after symbols; e.g

      for(int i=0; i< heap.length; i++){
    

    should be

      for (int i = 0; i < heap.length; i++) {
    
  • if(found == false) should be if (!found)

  • redundant (and inconsistent) use of this in the constructor.

And there are no javadocs!


Also, this looks like a bug:

    public int min(){
        return heap[1];   // should this be zero?
    }

Have you >>tested<< the code thoroughly?

\$\endgroup\$
0
\$\begingroup\$

Buggy

These lines of code suggests you want to use [1] as the first element:

    int parent = child/2;

    public int min(){
        return heap[1];
    }

The parent index can only be child/2 if [1] is the root of the heap. If [0] is the root, then the correct parent index would be (child-1)/2. Also, returning heap[1] for the min element also indicates you want the heap to start at [1]. However, you have these other lines of code that conflict with that goal:

    public MinHeap(){
        this.size = 2;
        heap = new int[size];
        this.pos = 0;
    }

Here, you should set this.pos = 1; because pos is where you add your next element.

    public void delete(int item){
        boolean found = false;
        int start = 0;
        for(int i = 0; i< heap.length; i++){

Here, you should start your for loop at index 1 instead of 0.

Later in the delete() function you have another bug:

        for(int i=pos; i > 0; i--){

The element at pos does not exist, so your loop needs to start at pos-1.

Inefficient delete

Right now, when you delete any element, you end up reheaping the entire heap. What you should actually do is move the last element into the deleted slot, and then fix the heap from the deleted slot only (you need to check both against the parent and against the children).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.