Как приоритетная очередь используется с кучей для решения минимального расстояния

Question

Пожалуйста, подождите, я новичок в структурах данных.

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

Однако меня смущает, как здесь используется очередь «куча + приоритет». Например, скажем, что я начинаю с (1,1) в сетке и хочу найти минимальное расстояние до (3,3). Я знаю, как реализовать алгоритм в смысле поиска соседей, проверки расстояний и отметки как посещенных. Но я читал о приоритетных очередях и минимальных кучах и хочу реализовать это.

Сейчас я понимаю только то, что приоритетная очередь имеет ключ для позиционирования элементов. Моя проблема в том, что когда я вставляю первых соседей (1,0),(0,0),(2,1),(1,2), они вставляются в pq на основе ключа (который в данном случае будет расстоянием). Таким образом, следующим поиском будет элемент в матрице с наименьшим расстоянием. Но с pq, как здесь можно использовать кучу с более чем двумя соседями? Например, дочерние элементы (1,1) - это 4 указанных выше соседа. Это будет go против 2*i и 2*i + 1 и i/2

В заключение, я не понимаю, как работает очередь min heap + priority с нахождением минимума чего-то вроде расстояния.

    0 1 2 3
     _ _ _ _
0 - |2|1|3|2|
1 - |1|3|5|1|
2 - |5|2|1|4|
3 - |2|4|2|1|

Answer 1

Вам необходимо использовать очередь приоритетов, чтобы получать минимальные веса при каждом движении, чтобы MinPQ подходил для этого. sink() swim()

Итак, MinPQ - это структура данных, которая использует метод кучи внутри

Answer 2

Если я правильно интерпретирую ваш вопрос, вы застряли на этом этапе:

Но с pq, как можно использовать кучу здесь с более чем двумя соседями? Например, дочерние элементы (1,1) - это 4 указанных выше соседа. Это будет go против 2 * i и 2 * i + 1 и i / 2

Похоже, что вас сбивает с толку, так это то, что здесь есть две отдельные концепции, которые вы можете комбинировать вместе . Во-первых, есть понятие «два места в сетке могут быть рядом друг с другом». В этом мире у вас есть (до) четырех соседей для каждой локации. Далее следует форма двоичной кучи, в которой каждый узел имеет двух дочерних узлов, расположение которых задается определенными арифметическими c вычислениями индексов массива. Они полностью независимы друг от друга - двоичная куча не знает, что элементы, которые она хранит, поступают из сетки, а сетка не знает, что существует массив, в котором каждый узел имеет двух дочерних узлов, хранящихся в определенных положениях.

Например, предположим, что вы хотите сохранить местоположения (0, 0), (2, 0), (-2, 0) и (0, 2) в двоичной куче, и что веса этих местоположений равны 1, 2 , 3 и 4 соответственно. Тогда форма двоичной кучи может выглядеть так:

               (0, 0)
              Weight 1
             /        \
          (2, 0)      (0, 2)
         Weight 2    Weight 4
           /
        (0, -2)
       Weight 3

Это дерево по-прежнему дает каждому узлу два дочерних элемента; эти дочерние элементы просто не обязательно сопоставляются с относительными позициями узлов в сетке.

В более общем смысле, относитесь к очереди с приоритетами как к черному ящику. Представьте, что это просто устройство magi c, которое говорит: «Вы можете дать мне новую вещь для хранения» и «Я могу дать вам самую дешевую вещь, которую вы пока что дали», и все. Тот факт, что внутренне он по совпадению реализован как двоичная куча, по сути не имеет значения.

Надеюсь, это поможет!