Вот собственно ещё одна тема и надеюсь не последняя. Я умею писать алгоритм дейкстры(http://e-maxx.ru/algo/dijkstra), но он работает неэффективно за O(n^2+m).Слышал что существует дейкстра кучей(heap) за O(nlogm). Если кто-нибудь знает объясните пожалуйста...

если на каждом шаге проводить не линейный поиск вершины с наименьшим весом, а пользоваться специальной структурой, алгоритм будет эффективнее. heap - пирамида (сбалансированное двоичное дерево определенного вида, обычно уложенное в массив), на основе которой естественным образом реализуется очередь с приоритетом (доступ к минимальному элементу O(1), удаление минимального O(logN))
heap
алгоритм дейкстры (включает обсуждение производительности)
реализация может быть основана на обобщенном обходе графа, основанном на очереди с приоритетом (dfs основан на стеке, bfs - на очереди, обобщенный - на произвольном контейнере). технически можно использовать bfs, заменив очередь на heap.

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

Получается,что я могу находить минимальное ребро за О(1) строя при этом min-кучу, но разве это будет не долго строить для каждой вершины heap?

Это сообщение отредактировал(а) altairaimenov - 22.5.2015, 07:29

И также я прочитав статью, не понял функцию heapify(https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%B0%D1%8F_%D0%BA%D1%83%D1%87%D0%B0)

Heapify(A, i)
  left ← 2i
  right ← 2i+1
  heap_size - количество элементов в куче
  largest ← i
  if left ≤ A.heap_size и A[left] > A[i]
    then largest ← left
  if right ≤ A.heap_size и A[right] > A[largest]
    then largest ← right
  if largest ≠ i
    then Обменять A[i] ↔ A[largest]
         Heapify(A, largest)

Ведь может быть так, что когда мы меняем местами нашего сына и предка, то может получиться так,что наш нынешний предок окажется больше своего предка, но функция этого не проверяет или я где-то не правильно понял?
Вот допустим у меня изменен элемент a[i], Я послал функцию heapify(a,i). И допустим,что он оказался больше своих сыновей.Функция это проверит и выйдет.Но ведь его предок (i/2) может быть меньше его.

P.s. это все относится к max-куче

Heapify применяется к массиву, где нарушено положение не более одного элемента


Добавлено через 2 минуты и 3 секунды

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