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

Question

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

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

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

Answer 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-свойство.

Вот моя реализация на C#: http://pastebin.com/kkZn123m

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

Важное примечание: использование значений для поиска индекса потребует, чтобы они были УНИКАЛЬНЫМИ. Если вы не согласны с этим условием, вам придется добавить какой-то уникальный идентификатор в ваши пары ключ-значение и поддерживать отображение между этим уникальным идентификатором и индексом кучи вместо отображения значения-индекса. Но для Dijkstra это не нужно, так как ваши значения будут узлами графа, и вы не хотите дублировать узлы в своей очереди приоритетов.

Answer 2

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

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

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

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

Answer 3

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

Answer 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