4
\$\begingroup\$

I have implemented a min heap and looking for a simpler solution.

Is there anyone for suggesting a simpler solution for this?

Thanks.

import com.sun.org.apache.xalan.internal.xsltc.dom.MultiValuedNodeHeapIterator;

import java.util.Arrays;

public class MinHeap {

    private int capacity = 10;
    private int size = 0;

    int[] items = new int[capacity];

    private int getLeftChildIndex(int parentIndex) { return 2 * parentIndex + 1 ;}
    private int getRightChildIndex(int parentIndex) { return 2 * parentIndex + 2 ;}
    private int getParentIndex(int childIndex) { return (childIndex -1) / 2 ;}

    private boolean hasLeftChild(int index) { return getLeftChildIndex(index) < size; }
    private boolean hasRightChild(int index) { return getRightChildIndex(index) < size; }
    private boolean hasParent(int index) { return getParentIndex(index) >= 0; }

    private int  leftChild(int index) { return items[getLeftChildIndex(index)]; }
    private int  rightChild(int index) { return items[getRightChildIndex(index)]; }
    private int  parent(int index) { return items[getParentIndex(index)]; }


    private void swap(int indexOne, int indexTwo){
        int temp = items[indexOne];
        items[indexOne] = items[indexTwo];
        items[indexTwo] = temp;
    }

    private void ensureExtraCapacity() {
        if (size == capacity) {
            items = Arrays.copyOf(items, capacity * 2);
            capacity *= 2;
        }
    }

    private int peek() {
        if (size == 0) throw new IllegalStateException();
        return items[0];
    }

    private int poll() {
        if (size == 0) throw new IllegalStateException();
        int item = items[0];
        items[0] = items[size - 1];
        size--;
        heapifyDown();
        return item;
    }

    public void add(int item) {
        ensureExtraCapacity();
        items[size] = item;
        size++;
        heapifyUp();
    }

    public void heapifyUp() {
        int index = size - 1;
        while ( hasParent(index) && parent(index) > items[index] ) {
            swap (getParentIndex(index),index);
            index = getParentIndex(index);
        }
    }

    public void heapifyDown() {
        int index = 0;
        while ( hasLeftChild(index) ) {
            int smallerChildIndex = getLeftChildIndex(index);
            if (hasRightChild(index) && rightChild(index) < leftChild(index)) {
                smallerChildIndex = getRightChildIndex(index);
            }

            if (items[index] < items[smallerChildIndex]) {
                break;
            } else {
                swap(index, smallerChildIndex);
            }
            index = smallerChildIndex;
        }
    }


}

\$\endgroup\$
1
\$\begingroup\$

I have one suggestion for your code.

  1. Create a method to check if the current size is invalid, and reuse it (MinHeap#peek and MinHeap#poll methods).
private void assertCurrentSizeIsValid() {
   if (size == 0) {
      throw new IllegalStateException();
   }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Almost the same with the current code that's ok. \$\endgroup\$ – Neslihan Bozer Apr 30 at 10:41

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.