2
\$\begingroup\$

I have implemented a java class for minHeap but it is not working as fast as I want . I want some help to change it to work faster in insertion or deleting the minimum node.

Here is my implementation:

public class MinHeap {
    private static final int d = 2;
    private int heapSize;
    private long[] heap;

    MinHeap(int capacity) {
        heapSize = 0;
        heap = new long[capacity + 1];
        Arrays.fill(heap, -1);
    }

    boolean isEmpty() {
        return heapSize == 0;
    }

    boolean isFull() {
        return heapSize == heap.length;
    }

    private int parent(int i) {
        return (i - 1) / d;
    }

    private int kthChild(int i, int k) {
        return d * i + k;
    }

    void insert(long x) {
        if (isFull())
            throw new NoSuchElementException("Overflow Exception");
        heap[heapSize++] = x;
        bubbleUp(heapSize - 1);
    }

    long findMin() {
        if (isEmpty())
            throw new NoSuchElementException("Underflow Exception");
        return heap[0];
    }

    void deleteMin() {
        delete(0);
    }

    void delete(int ind) {
        if (isEmpty())
            throw new NoSuchElementException("Underflow Exception");
        heap[ind] = heap[heapSize - 1];
        heapSize--;
        bubbleDown(ind);
    }

    private void bubbleUp(int childInd) {
        long tmp = heap[childInd];
        while (childInd > 0 && tmp < heap[parent(childInd)]) {
            heap[childInd] = heap[parent(childInd)];
            childInd = parent(childInd);
        }
        heap[childInd] = tmp;
    }

    private void bubbleDown(int ind) {
        int child;
        long tmp = heap[ind];
        while (kthChild(ind, 1) < heapSize) {
            child = minChild(ind);
            if (heap[child] < tmp)
                heap[ind] = heap[child];
            else
                break;
            ind = child;
        }
        heap[ind] = tmp;
    }

    private int minChild(int ind) {
        int bestChild = kthChild(ind, 1);
        int k = 2;
        int pos = kthChild(ind, k);
        while ((k <= d) && (pos < heapSize)) {
            if (heap[pos] < heap[bestChild])
                bestChild = pos;
            pos = kthChild(ind, k++);
        }
        return bestChild;
    }

}

Thanks in advance for your help!

\$\endgroup\$
5
  • \$\begingroup\$ @greybeard Thanks for your comment, sorry I made a mistake, I had to delete the method maxElementIndex, It was related to the code I wrote for a special program, it is not in the minHeap implementation. \$\endgroup\$
    – b.j
    Feb 23 '20 at 17:28
  • 1
    \$\begingroup\$ Welcome to CodeReview@SE. How did you establish minHeap [deleteMin() and insert() are] not working as fast as I want? When in doubt, use a microbenchmarking framework. To check improvement suggestions, usage context, sample data or a test data generator would be useful. \$\endgroup\$
    – greybeard
    Feb 23 '20 at 17:28
  • \$\begingroup\$ (What about java.util.PriorityQueue/java.util.concurrent.PriorityBlockingQueue?) \$\endgroup\$
    – greybeard
    Feb 23 '20 at 17:39
  • \$\begingroup\$ @greybeard I do not know what is the main problem, I'm implementing this for a homework assignment and I get two of the test cases as "time limit exceeded", I asked my teacher what is the reason and he said I can get a faster implementation of my minHeap. I have also tried PriorityQueue but still does not work:( \$\endgroup\$
    – b.j
    Feb 24 '20 at 7:02
  • 1
    \$\begingroup\$ Welcome to CodeReview, as suggested by greybeard it would be useful posting here test cases (input and output) indicating which ones ended with time limit exceeded. \$\endgroup\$ Feb 24 '20 at 8:51
2
\$\begingroup\$

Without more information what, when asked for a reason for two "time limit exceeded" results, motivated your teacher to mention the possibility to "get" a faster minHeap, you deprive yourself of getting more useful answers. See How to get the best value out of Code Review - Asking Questions
First and foremost, just what is the task timed?
I can't see anything seriously detrimental in your implementation:
I guess a bigger task than, say, handle a batch of insertions and min extractions gets timed, in need of an algorithmic improvement more likely than any tuning.


That said, there are principles like YAGNI, KISS and DRY.
Let me start with the bright side of YAGNI - You Are Gonna Need It:

Otherwise, the code presented looks a pretty decent beginner's stab at coding a heap.
Catch:

  • There are omissions from the deletes:
    not relevant when using an array of primitives as presented in the question:
     Failing to set the reference at the index deallocated to something innocent (as null) does not immediately impede garbage collection, as it gets copied to a lower index. Enter the next delete
    • bug in delete(int d):
      It replaces element atD with formerLast and restores the heap relations in formerLast and its descendants.
      But what about its ancestors?
      Not to worry if
      1) it ends up at an index abode d or
      a) it was a descendant of atD: none of those has higher priority
      There are many ways to handle the situation -
      I'd prefer just dropping delete(int d) over just calling bubbleUp() or some elaborate handling trying to keep the number of comparisons low.

Room for improvement:

  • Part of Don't Repeat Yourself is using interfaces:
    Define an interface for an, um, PriorityCollection<E> extends Collection<E>.
    One advantage is that implementations don't get to reduce visibility of interface methods like isEmpty().
    Another is inheriting documentation, too.
    • have an E extractTop() return the top priority element it just removed from the Collection
    • nowadays, Java interfaces can include unit test code, too.
  • Keep It Short&Simple meets You Ain't Gonna Need It in fixing arity at 2:
    • simpler/shorter code
    • fixes a naming issue in d (maximal degree?)
    • maximises information in relative position of keys
    • doesn't show in the interface, anyway

If and when competent (→ framework) measurements suggest the performance being a problem,
• consider returning to an array of primitives.
If the cost of comparing elements is high, change tactics in bubbleDown(sink?): find the path along which to sink/bubble down, and look for elements that should stay in place starting from the bottom: this may almost half the number of comparisons.
• an E replaceTop(E replacement) may save considerable work
  it may be useful to additionally have the similar E addAndExtractTop(E addition)

\$\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.