Реализация минимальной кучи с массивом: вставьте и удалите минимальную (с дубликатами)

Question

Я пытаюсь реализовать Min Heap в Java, но у меня возникают проблемы со вставкой и удалением элементов (вставка в конце, удаление корня как мин). Похоже, что это работает по большей части (я использую программу для визуального отображения кучи и распечатывал новые корни после удаления min, и тому подобное).

Моя проблема в том, что по какой-то причине корень не будет переключаться с новым элементом при добавлении нового элемента, но я вообще не могу понять, почему. Кроме того, кажется, что это единственная проблема, когда имеется много дубликатов, а куча, похоже, не совсем способна оставаться в порядке (родительский элемент меньше дочерних). По большей части, это так. Только иногда это не так, и мне кажется, что это случайно.

Это делается с помощью обобщений и в основном следует большинству алгоритмов. Все остальное, что я знаю, на самом деле работает, это определенно проблема с этими двумя методами.

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
}

Любые переменные, не объявленные в методах, являются глобальными, и я знаю, что некоторые вещи, вероятно, являются избыточными, например, вся текущая / последняя / временная ситуация в add, поэтому я сожалею об этом. Я попытался сделать все имена понятными и объяснить все проверки, которые я делал в removeMin. Любая помощь будет безумно признательна, я дошел до того, что могу искать вещи и отлаживать их. Я думаю, что я просто что-то здесь упускаю.

Answer 1

Просто чтобы помочь вам отладить, вы должны упростить код. Что-то странное происходит с переменной 'last'. Также в 'insert', когда вы делаете цикл, вероятно, temp должен перейти к 0, то есть

while (temp >= 0 &&......