Как реализовать операцию уменьшения ключа O (logn) для очереди приоритетов с мини-кучей?

Я работаю над приложением, демонстрирующим алгоритм Djikstra, и для его использования мне нужно восстановить свойство кучи, когда значение моих элементов уменьшено.

Проблема сложности заключается в том, что , когда алгоритм изменяет значение элемента, этот индекс элемента во внутренней структуре (куча в этом случае) используется для очереди приоритетов неизвестен. Таким образом, в настоящее время мне нужно выполнить поиск O (n), чтобы восстановить индекс, прежде чем я смогу выполнить на нем фактическое сокращение.

Кроме того, я не совсем уверен в фактическом коде, который необходим для операции. Я использую D-Heap здесь для моей очереди приоритетов. Pseudocode поможет, но я предпочел бы пример в Java о том, как это сделать.

Ответы

Ответ 1

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

on Swap(i, j): 
    map[value[i]] = j; 
    map[value[j]] = i;

on Insert(key, value): 
    map.Add(value, heapSize) in the beginning;

on ExtractMin: 
    map.Remove(extractedValue) in the end;

on UpdateKey(value, newKey): 
    index = map[value]; 
    keys[index] = newKey;

BubbleUp(index) в случае DecreaseKey и BubbleDown/Heapify(index) в случае IncreaseKey восстановить свойство min-heap.

Здесь моя реализация С#: http://pastebin.com/kkZn123m

Вставка и ExtractMin вызов Swap log (N) раз, при восстановлении свойства кучи. И вы добавляете O (1) накладные расходы на Swap, поэтому обе операции остаются O (log (n)). UpdateKey также является log (N): сначала вы индексируете индекс в хэш-карте для O (1), тогда вы восстанавливаете свойство кучи для O (log (N)), как вы это делаете в Insert/ExtractMin.

Важное примечание: использование значений для поиска индекса потребует, чтобы они были UNIQUE. Если вы не согласны с этим условием, вам нужно будет добавить некоторый уникальный идентификатор к вашим парам ключ-значение и поддерживать сопоставление между этим уникальным идентификатором id и индексом кучи вместо преобразования значений-индекса. Но для Dijkstra это не нужно, так как ваши значения будут узлами графа, и вы не хотите дублировать узлы в очереди приоритетов.

Ответ 2

Per этот вопрос SO, нет необходимости использовать метод уменьшения ключа для реализации алгоритма Дейкстры.

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

Наличие большого количества дополнительных узлов в очереди приоритетов не является проблемой, поскольку это структура O(log N). (Вы должны сделать около 20 сравнений для 1 миллиона предметов и 30 сравнений для 1 миллиарда элементов.)

Изменить: В ответ на этот вопрос позже я немного разочарован моим ответом: все эти вещи должны будут оторваться от очереди, если вы не сделаете какие-то специальные приемы позже. Как и многие вещи в жизни, все сводится к тому, как вы управляете своей памятью и затратами, связанными с этим. Но общая точка остается: клавиша уменьшения не нужна, даже если это может быть желательно.

Ответ 3

Если вы используете С++ stl make_heap()/pop_heap()/push_heap(), нет способа сохранить индекс от node id для индексации в векторе кучи подчеркивания, я думаю, вы должны реализовать свою собственную кучу функции для достижения O (logn) в операции "Увеличение ключа/уменьшения".

Ответ 4

Я реализовал то же самое. В классе MinHeap я добавил словарь, который используется для доступа к элементу в O (1). А при уменьшении ключ будет всплывать за время O (logn).

class MinHeap:
def __init__(self, array):
    self.heap = self.buildHeap(array)
    self.idx_of_element = {}

def getParentIdx(self, idx):
    return (idx - 1) // 2

def getLeftChildIdx(self, idx):
    return idx * 2 + 1

def getRightChildIdx(self, idx):
    return idx * 2 + 2

def buildHeap(self, array):
    # Write your code here.
    lastIdx = len(array) - 1
    startFrom = self.getParentIdx(lastIdx)
    for i in range(startFrom, -1, -1):
        self.siftDown(i, array)
    return array

# this is min-heapify method
def siftDown(self, idx, array):
    while True:
        l = self.getLeftChildIdx(idx)
        r = self.getRightChildIdx(idx)

        smallest = idx
        if l < len(array) and array[l] < array[idx]:
            smallest = l
        if r < len(array) and array[r] < array[smallest]:
            smallest = r

        if smallest != idx:
            array[idx], array[smallest] = array[smallest], array[idx]
            self.idx_of_element[self.heap[idx]], self.idx_of_element[self.heap[smallest]] = self.idx_of_element[self.heap[smallest]], self.idx_of_element[self.heap[idx]]
            idx = smallest
        else:
            break