Нужна помощь Подсчет количества свопов в MaxHeap - PullRequest
Новая
       62

Нужна помощь Подсчет количества свопов в MaxHeap

0 голосов
/ 22 апреля 2019

В настоящее время я работаю над проектом, в котором мне нужно создать максимальную кучу. В настоящее время я использую версию кучи из учебников, которая выглядит примерно так: 

public MaxHeap(int initialCapacity) {
    if (initialCapacity < DEFAULT_CAPACITY)
        initialCapacity = DEFAULT_CAPACITY;
    else
        checkCapacity(initialCapacity);

    @SuppressWarnings("unchecked")
    T[] tempHeap = (T[]) new Comparable[initialCapacity + 1];
    heap = tempHeap;
    lastIndex = 0;
    initialized = true;
}

public T getMax() {
    checkInitialization();
    T root = null;
    if (!isEmpty())
        root = heap[1];
    return root;
}

public boolean isEmpty() {
    return lastIndex < 1;
}

public int getSize() {
    return lastIndex;
}

public void clear() {
    checkInitialization();
    while (lastIndex > -1) {
        heap[lastIndex] = null;
        lastIndex--;
    }
    lastIndex = 0;
}

public void add(T newEntry) {
    checkInitialization();
    int newIndex = lastIndex + 1;
    int parentIndex = newIndex / 2;
    while ((parentIndex > 0) && newEntry.compareTo(heap[parentIndex]) > 0) {
        heap[newIndex] = heap[parentIndex];
        newIndex = parentIndex;
        parentIndex = newIndex / 2;
    }
    heap[newIndex] = newEntry;
    lastIndex++;
    ensureCapacity();
}

public int getSwaps()
{
    return swaps;
}

public T removeMax() {
    checkInitialization();
    T root = null;
    if (!isEmpty()) {
        root = heap[1];
        heap[1] = heap[lastIndex];
        lastIndex--;
        reheap(1);
    }
    return root;
}

private void reheap(int rootIndex) {
    boolean done = false;
    T orphan = heap[rootIndex];
    int leftChildIndex = 2 * rootIndex;

    while (!done && (leftChildIndex <= lastIndex)) {
        int largerChildIndex = leftChildIndex;
        int rightChildIndex = leftChildIndex + 1;
        if ((rightChildIndex <= lastIndex) && heap[rightChildIndex].compareTo(heap[largerChildIndex]) > 0) {
            largerChildIndex = rightChildIndex;
        }
        if (orphan.compareTo(heap[largerChildIndex]) < 0) {
            heap[rootIndex] = heap[largerChildIndex];
            rootIndex = largerChildIndex;
            leftChildIndex = 2 * rootIndex;
        } else
            done = true;
    }
    heap[rootIndex] = orphan;

}

Должен ли я подсчитывать свопы в нескольких местах и ​​распечатывать общую сумму, и если да, то где бы я их посчитал? Ранее я пытался просто перечислить swaps ++ в методе add, но я не думаю, что это правильный способ сделать это.

Ответы [ 2 ]

1 голос
/ 22 апреля 2019

Будет ли это правильным способом реализации?

Таким образом, метод добавления будет: 

public void add(T newEntry) {
checkInitialization();
int newIndex = lastIndex + 1;
int parentIndex = newIndex / 2;
while ((parentIndex > 0) && newEntry.compareTo(heap[parentIndex]) > 0) {
    heap[newIndex] = heap[parentIndex];
    newIndex = parentIndex;
    parentIndex = newIndex / 2;
    swap++;
}
heap[newIndex] = newEntry;
lastIndex++;
ensureCapacity();
}

и повторная таблица будет: 

private void reheap(int rootIndex) {
boolean done = false;
T orphan = heap[rootIndex];
int leftChildIndex = 2 * rootIndex;

while (!done && (leftChildIndex <= lastIndex)) {
    int largerChildIndex = leftChildIndex;
    int rightChildIndex = leftChildIndex + 1;
    if ((rightChildIndex <= lastIndex) && heap[rightChildIndex].compareTo(heap[largerChildIndex]) > 0) {
        largerChildIndex = rightChildIndex;
    }
    if (orphan.compareTo(heap[largerChildIndex]) < 0) {
        heap[rootIndex] = heap[largerChildIndex];
        rootIndex = largerChildIndex;
        leftChildIndex = 2 * rootIndex;
        swap++;
    } else
        done = true;
}
heap[rootIndex] = orphan;

}
1 голос
/ 22 апреля 2019

Вы должны посчитать своп как в методе add(T newEntry), так и в методе reHeap, который вызывается из removeMax mathod.

В reHeap вы начинаете сверху и по мере его вызоваиз removeMax, где после удаления max (в случае Max Heap) вы заменяете корень последним элементом, а затем вам необходимо сбалансировать кучу.Таким образом, куча рекурсивно снижается до последнего уровня для балансировки, что может потребовать подкачки.

РЕДАКТИРОВАТЬ:

Добавить подкачку внутри следующего блока кода reHeap: 

if (orphan.compareTo(heap[largerChildIndex]) < 0) {
        heap[rootIndex] = heap[largerChildIndex];
        rootIndex = largerChildIndex;
        leftChildIndex = 2 * rootIndex;
        // increment the swap here as inside this block of reHeap only swap takes place.
        swap++
 }
...