Что это на самом деле означает под разными кучами?

Question

Существуют различные операции с кучей, и одним и тем же операциям присваиваются различные имена.

Я поражен именами и псевдонимами.

Поэтому, пожалуйста, поясните, в чем различия / сходства/ отношения между следующими heap-операциями:

(1) Heapify
(2) Insert
(3) Delete
(4) Shift-up
(5) Shift-down

Например, некоторые ресурсы говорят о реализации Heapsort с использованием shift-down;в то время как некоторые реализовали тот же алгоритм, используя Heapify.Некоторые даже реализовали это, используя Delete.

Answer 1

1) Heapify восстанавливает состояние кучи. Например, если вы изменили узел в дереве, условие больше не действует. Вы можете восстановить условие, если переместите свои узлы вверх или вниз по дереву.

2) Вставить узел в дерево

3) Удалить узел в дереве

4) Перемещать узел вверх по дереву столько, сколько необходимо (в зависимости от состояния кучи: min-heap или max-heap)

5) Переместить узел вниз в дереве, аналогично 4)

Вероятно, будет лучше, если вы попытаетесь реализовать или понять реальный код и не беспокоиться о наименовании ..

Answer 2

Чтобы добавить примечание к ответу с помощью @ duedl0r, для чего используется сдвиг вверх и вниз, это heapify текущей структуры. Так, например. в случае минимальной кучи, когда вы вставляете элемент, который меньше, чем некоторые узлы в дереве, структура данных теперь не соответствует условию кучи (в случае минимальной кучи значение parent должно быть меньше его дочерних элементов), поэтому Вы должны сдвигаться вверх и вверх.

Итак, с точки зрения кода:

public void insert(int value) {
    if (heapSize == data.length)
        throw new HeapException("Heap's underlying storage is overflow");

    else {
        heapSize++;
        data[heapSize - 1] = value;
        siftUp(heapSize - 1);
    }

}    

private void siftUp(int nodeIndex) {
    int parentIndex, tmp;
    if (nodeIndex != 0) {
        parentIndex = getParentIndex(nodeIndex);
        /*if parent index data is more than child data, swap*/
        if (data[parentIndex] > data[nodeIndex]) {
            tmp = data[parentIndex];
            data[parentIndex] = data[nodeIndex];
            data[nodeIndex] = tmp;
            siftUp(parentIndex);
        }
    }

}

data - это массив для повторения кучи, а heapSize - это текущее место, где будет храниться новый элемент, и он сообщает, что эта куча заполнена.

Аналогично, в случае удаления вы должны использовать shift вниз, чтобы реструктурировать вашу кучу.

Answer 3

Загляните в Википедию, и вы можете получить всевозможную информацию о кучах:

http://en.wikipedia.org/wiki/Heap_%28data_structure%29