# Optimizing minHeap implementation

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;
}

}


• @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.
– b.j
Feb 23 '20 at 17:28
• 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. Feb 23 '20 at 17:28
• Feb 23 '20 at 17:39
• @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:(
– b.j
Feb 24 '20 at 7:02
• 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. Feb 24 '20 at 8:51

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.
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)