I'm trying to implement a Min Heap in Java, but I'm having issues with inserting and removing elements (inserting at the end, removing the root as min). It seems to work for the most part (I use a program to visually display the heap and have been printing out the new roots when min has been removed, things like that).

My problem is, for some reason the root won't switch with a new item when a new item is added, but I can't figure out why at all. Also, it seems this is only the problem when there are a lot of duplicates, the heap doesn't seem completely capable of staying in order (the parent is smaller than the children). For the most part, it does. Only occasionally it doesn't, and to me it seems random.

This is done with generics, and basically following most algorithms. Everything else I know for a fact works, it's definitely a problem with these two methods.

Any variables not declared in the methods are global, and I know a couple of things are probably redundant, like the whole current/last/temp situation in add, so I'm sorry about that. I tried to make all names self explanatory and explain all the checks I did in removeMin. Any help would be insanely appreciated, I've gotten as far as I can looking things up and debugging. I think I'm just fundamentally missing something here.PHP Code:

`public void insert(T e) {`

if (size == capacity)

increaseSize(); //this works fine

last = curr; //keeping track of the last index, for heapifying down/bubbling down when removing min

int parent = curr/2;

size++; //we added an element, so the size of our data set is larger

heap[curr] = e; //put value at end of array

//bubble up

int temp = curr;

while (temp > 1 && ((Comparable<T>) heap[temp]).compareTo(heap[parent]) < 0) { //if current element is less than the parent

//integer division

parent = temp/2;

swap(temp, parent); //the swapping method should be correct, but I included it for clarification

temp = parent; //just moves the index value to follow the element we added as it is bubbled up

}

curr++; //next element to be added will be after this one

}

public void swap(int a, int b){

T temp = heap[a];

heap[a] = heap[b];

heap[b] = temp;

}

public T removeMin() {

//root is always min

T min = heap[1];

//keep sure array not empty, or else size will go negative

if (size > 0)

size--;

//put last element as root

heap[1] = heap[last];

heap[last] = null;

//keep sure array not empty, or else last will not be an index

if (last > 0)

last--;

//set for starting at root

int right = 3;

int left = 2;

int curr = 1;

int smaller = 0;

//fix heap, heapify down

while(left < size && right < size){ //we are in array bounds

if (heap[left] != null && heap[right] != null){ //so no null pointer exceptions

if (((Comparable<T>)heap[left]).compareTo(heap[right]) < 0) //left is smaller

smaller = left;

else if (((Comparable<T>)heap[left]).compareTo(heap[right]) > 0) //right is smaller

smaller = right;

else //they are equal

smaller = left;

}

if (heap[left] == null || heap[right] == null)//one child is null

{

if (heap[left] == null && heap[right] == null)//both null, stop

break;

if (heap[left] == null)//right is not null

smaller = right;

else //left is not null

smaller = left;

}

if (((Comparable<T>)heap[curr]).compareTo(heap[smaller]) > 0)//compare smaller or only child

{

swap(curr,smaller); //swap with child

curr = smaller; //so loop can check new children for new placement

}

else //if in order, stop

break;

right = 2*curr + 1; //set new children

left = 2*curr;

}

return min; //return root

}