Продолжаю совмещать приятное с полезным и переводить. Сегодня речь зайдет о кучах (heaps) и графах. Как обычно, материал скорее подойдет новичкам — большая часть информации, если не вся, уже где-то так или иначе освещалась.
В конце прошлой статьи затрагивались деревья, поэтому начнем с кучи, поскольку между кучей и деревьями есть общие корни. Затем перейдем к графам и реализуем алгоритм Дейкстры.
Куча — специальная, деревоподобная структура, у которой есть одно свойство — любой родительский узел всегда больше либо равен своим потомкам. Таким образом, при выполнении данного условия, корневой элемент кучи всегда будет максимальным. Данный вариант называют максимальной (полной) кучей или maxheap. Куча, где корневой элемент минимален, а каждый родительский узел меньше или равен своим потомкам — минимальная куча или minheap.
Двоичную кучу (maxheap) можно представить таким образом:
Она является двоичной потому, что каждый родитель имеет два потомка.
Стоит отметить, что кучи хоть и реализуются как бинарные деревья, но у них нет такого понятия как упорядочивание и нет определенного порядка для обхода. Куча — вариант табличной структуры, поэтому к ней применимы следующие базовые операции:
- create – создать пустую кучу.
- isEmpty – определить, пуста ли куча или нет.
- insert – добавить элемент в кучу.
- extract – извлечь и удалить элемент (корень, вершину) из кучи.
Поскольку операции получения и удаления элементов совмещены в одной операции извлечения, то для начала ее и рассмотрим.
Правило для удаления элемента из кучи состоит в том, что удалять можно только корневой элемент. Допустим, мы удалили корневой элемент из примера выше (100). После удаления мы останемся с двумя раздельными кучами и нам нужно как-то пересобрать все это в одну отдельную кучу. Легче всего это сделать перемещением последнего узла в корень, однако в таком случае такая куча не будет подходить по основному условию. Такая куча называется semiheap:
Теперь надо сделать из полукучи нормальную кучу. Одно из возможных решений этой проблемы — спускать новый корень вниз, попутно сравнивая корневой элемент с его потомками и меняя его местами с максимальным потомком. Таким образом, мы вернем в корень максимальный элемент, при этом опустив минимальный максимально вниз.
Мы можем реализовать maxheap как массив. Узел в бинарном дереве не может иметь более двух потомков, поэтому для любого количества узлов n бинарная куча будет иметь 2n+1 узел.
Реализуем кучу следующим образом:
<?php
class BinaryHeap
{
protected $heap;
public function __construct() {
$this->heap = array();
}
public function isEmpty() {
return empty($this->heap);
}
public function count() {
// возвращаем размер кучи
return count($this->heap) - 1;
}
public function extract() {
if ($this->isEmpty()) {
throw new RunTimeException('Куча пуста!');
}
// извлечем первый элемент из кучи и присвоим его как корень
$root = array_shift($this->heap);
if (!$this->isEmpty()) {
// переместим последний элемент кучи на ее вершину
// чтобы избавиться от двух разделенных между собой ветвей
$last = array_pop($this->heap);
array_unshift($this->heap, $last);
// превратим полукучу в кучу
$this->adjust(0);
}
return $root;
}
public function compare($item1, $item2) {
if ($item1 === $item2) {
return 0;
}
// обратное сравнение даст нам minheap
return ($item1 > $item2 ? 1 : -1);
}
protected function isLeaf($node) {
// здесь всегда будет 2n + 1 узел в "подкуче"
return ((2 * $node) + 1) > $this->count();
}
protected function adjust($root) {
// спускаемся как можно ниже
if (!$this->isLeaf($root)) {
$left = (2 * $root) + 1; // левый потомок
$right = (2 * $root) + 2; // правый потомок
$h = $this->heap;
// если корень меньше своих потомков
if (
(isset($h[$left]) &&
$this->compare($h[$root], $h[$left]) < 0)
|| (isset($h[$right]) &&
$this->compare($h[$root], $h[$right]) < 0)
) {
// находим старшего потомка
if (isset($h[$left]) && isset($h[$right])) {
$j = ($this->compare($h[$left], $h[$right]) >= 0)
? $left : $right;
}
else if (isset($h[$left])) {
$j = $left; // левый потомок
}
else {
$j = $right; // правый потомк
}
// меняем местами с корнем
list($this->heap[$root], $this->heap[$j]) =
array($this->heap[$j], $this->heap[$root]);
// рекурсивно перебираем кучу относительно
// нового корневого узла $j
$this->adjust($j);
}
}
}
}
Вставка же наоборот, полная противоположность извлечению: мы вставляем элемент вниз кучи и поднимаем ее до тех пор, пока это возможно и выполняется главное условие. Так как мы знаем, что полное бинарное дерево содержит n/2 + 1 узел, мы можем обходить кучу используя простой бинарный поиск.
public function insert($item) {
// вставим новые элементы в конец кучи
$this->heap[] = $item;
// определим им корректное место
$place = $this->count();
$parent = floor($place / 2);
// пока не на вершине и больше родителя
while (
$place > 0 && $this->compare(
$this->heap[$place], $this->heap[$parent]) >= 0
) {
// меняем местами
list($this->heap[$place], $this->heap[$parent]) =
array($this->heap[$parent], $this->heap[$place]);
$place = $parent;
$parent = floor($place / 2);
}
}
Посмотрим что у нас получилось и попробуем вставить несколько значений в кучу:
<?php
$heap = new BinaryHeap();
$heap->insert(19);
$heap->insert(36);
$heap->insert(54);
$heap->insert(100);
$heap->insert(17);
$heap->insert(3);
$heap->insert(25);
$heap->insert(1);
$heap->insert(67);
$heap->insert(2);
$heap->insert(7);
Если мы попробуем вывести все это, то получим следующее:
Array
(
[0] => 100
[1] => 67
[2] => 54
[3] => 36
[4] => 19
[5] => 7
[6] => 25
[7] => 1
[8] => 17
[9] => 2
[10] => 3
)
Как видно, порядок не соблюден и вообще это несколько другое, что мы ожидали. Однако если мы будем по-очереди извлекать элементы из кучи, то все будет нормально:
<?php
while (!$heap->isEmpty()) {
echo $heap->extract() . "n";
}
100
67
54
36
25
19
17
7
3
2
1
SplMaxHeap и SplMinHeap
К счастью, для нас уже есть готовые реализации SplHeap, SplMaxHeap и SplMinHeap. Все что нам нужно сделать это только унаследовать их и переопределить метод сравнения, например так:
<?php
class MyHeap extends SplMaxHeap
{
public function compare($item1, $item2) {
return (int) $item1 - $item2;
}
}
Данный метод выполнит любое сравнение двух узлов и в случае SplMaxHeap он возвращает положительное число если $item1 больше $item2, 0 если они равны друг другу и отрицательное, если $item2 больше $item1. Если мы наследуем SplMinHeap, то он вернет положительное число, если $item1 меньше $item2.
Не рекомендуется помещать в кучу несколько одинаковых элементов, посколько их позицию будет трудно определить
SplPriorityQueue — приоритетная очередь
Приоритетная очередь это специальный абстрактный тип данных, который ведет себя как очередь, но реализуется как куча. В отношении SplPriorityQueue это будет maxheap. Приоритетная очередь имеет довольно много реальных применений, например, система тикетов или справочная служба.
Как и в случае SplHeap, нужно лишь унаследовать SplPriorityQueue и переопределить метод сравнения:
<?php
class PriQueue extends SplPriorityQueue
{
public function compare($p1, $p2) {
if ($p1 === $p2) return 0;
// в порядке возрастания приоритета, меньшее значение
// означает больший приоритет
return ($p1 < $p2) ? 1 : -1;
}
}
Основное отличие в SplPriorityQueue заключается в том, что при вставке, помимо значения элемента, ожидается еще и приоритет данного элемента. Операция вставки использует приоритет, чтобы просеивать кучу, основываясь на результате, который возвращает ваш компаратор.
Проверим работу приоритетной очереди, в качестве чисел зададим приоритет:
<?php
$pq = new PriQueue();
$pq->insert('A', 4);
$pq->insert('B', 3);
$pq->insert('C', 5);
$pq->insert('D', 8);
$pq->insert('E', 2);
$pq->insert('F', 7);
$pq->insert('G', 1);
$pq->insert('H', 6);
$pq->insert('I', 0);
while ($pq->valid()) {
print_r($pq->current());
echo "n";
$pq->next();
}
Что в итоге выдаст нам следующее:
I
G
E
B
A
C
H
F
D
В данном случае наши элементы идут в порядке убывания приоритета — от самого высокого к самому низкому (меньшее значение — больший приоритет). Можно поменять порядок выдачи элементов просто изменив метод сравнения, чтобы тот возвращал положительное число, если $p1 больше чем $p2.
По-умолчанию, извлекается только значение элемента. Если нужно получать только значения приоритета, или же значения и их приоритет, нужно установить соответствующий флаг извлечения:
<?php
// извлечь только приоритет
$pq->setExtractFlags(SplPriorityQueue::EXTR_PRIORITY);
// значение и приоритет (возвратит ассоциативный массив
// для каждого элемента)
$pq->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
Графы
За графами стоит довольно много реальных применений — оптимизация сетей, маршрутизация или же анализ социальных сетей. Google PageRank, рекомендации от Amazon — вот некоторые примеры их использования. В этой части статьи я попробую объяснить две задачи, в которых они используются — проблемы поиска короткого пути и наименьшее число остановок.
Граф — математическая конструкция, используемая для представления отношений между парами ключ-значение. Граф состоит из набора вершин (узлов) и произвольного числа связей между узлами, соединяющих их между собой. Эти связи могут быть направленными (ориентированными) и ненаправленными. Направленная связь это связь между двумя узлами и связь A→B не является тем же самым, что и B→A. Ненаправленная же связь не имеет направления, таким образом связи A-B и B-A являются идентичными. Основываясь на этих правилах можно сказать, что деревья являются одним из ненаправленных графов, где каждая вершина соединена с одним из узлов простой связью.
Графы также могут иметь вес. Взвешенный граф, или сеть — граф, у которого для каждой связи указан вес («цена» перехода из узла A в узел B). Такие конструкции широко используются для определения наиболее оптимального пути, или же наиболее «дешевого» пути между двумя точками. Прокладка пути в GoogleMap осуществляется при помощи именно взвешенного графа.
Минимальное число остановок (прыжков)
Общее применение теории графов используется при поиске минимального числа остановок между двумя узлами. Что касается деревьев, то здесь графы помогают в обходе дерева в одном из двух направлений — в глубину или в ширину. Поскольку в прошлый раз мы рассматривали поиск в глубину, то сейчас взглянем на другой метод.
Представим следующий граф:
Для простоты условимся, что данный граф ненаправленный. Задача — найти минимальное количество остановок между двумя любыми узлами. При поиске в ширину мы начинаем с корня (ну или с другого узла, который мы обозначили как корень) и спускаемся по дереву уровень за уровнем. Чтобы это реализовать нам нужна очередь для организации списка узлов, которые мы еще не обошли, чтобы возвращаться к нему и обрабатывать его каждый уровень. Общий алгоритм такой:
- 1. Создать очередь
- 2. Добавляем туда корневой элемент и помечаем его как посещенный
- 3. До тех пор пока очередь не пуста:
-
- 3a. извлекаем текущий узел
- 3b. если текущий узел является искомым — останавливаемся
- 3c. иначе добавляеем в очередь каждый непосещенный соседний узел и помечаем его как посещенный
Но как мы узнаем какие узлы соседние или непосещенные не прибегая к обходу графа? Это подводит нас к вопросу о том, как графы могут быть смоделированы.
Представление графа
Обычно, графы представляются двумя способами — таблица или матрица, где описаны соседние узлы.
Вот как это выглядит для первого примера:
В матрице, на пересечении узлов ставится «1», если узлы являются соседями.
Список удобен в том случае, если большая часть вершин не имеют связей между собой, матрица же обеспечивает более быстрый поиск. В конце концов вид представления графа зависит от того, какие операции с графом будут производиться. Мы воспользуемся списком.
<?php
$graph = array(
'A' => array('B', 'F'),
'B' => array('A', 'D', 'E'),
'C' => array('F'),
'D' => array('B', 'E'),
'E' => array('B', 'D', 'F'),
'F' => array('A', 'E', 'C'),
);
И напишем наш поиск в ширину:
<?php
class Graph
{
protected $graph;
protected $visited = array();
public function __construct($graph) {
$this->graph = $graph;
}
// найдем минимальное число прыжков (связей) между 2 узлами
public function breadthFirstSearch($origin, $destination) {
// пометим все узлы как непосещенные
foreach ($this->graph as $vertex => $adj) {
$this->visited[$vertex] = false;
}
// пустая очередь
$q = new SplQueue();
// добавим начальную вершину в очередь и пометим ее как посещенную
$q->enqueue($origin);
$this->visited[$origin] = true;
// это требуется для записи обратного пути от каждого узла
$path = array();
$path[$origin] = new SplDoublyLinkedList();
$path[$origin]->setIteratorMode(
SplDoublyLinkedList::IT_MODE_FIFO|SplDoublyLinkedList::IT_MODE_KEEP
);
$path[$origin]->push($origin);
$found = false;
// пока очередь не пуста и путь не найден
while (!$q->isEmpty() && $q->bottom() != $destination) {
$t = $q->dequeue();
if (!empty($this->graph[$t])) {
// для каждого соседнего узла
foreach ($this->graph[$t] as $vertex) {
if (!$this->visited[$vertex]) {
// если все еще не посещен, то добавим в очередь и отметим
$q->enqueue($vertex);
$this->visited[$vertex] = true;
// добавим узел к текущему пути
$path[$vertex] = clone $path[$t];
$path[$vertex]->push($vertex);
}
}
}
}
if (isset($path[$destination])) {
echo "из $origin в $destination за ",
count($path[$destination]) - 1,
" прыжков";
$sep = '';
foreach ($path[$destination] as $vertex) {
echo $sep, $vertex;
$sep = '->';
}
echo "n";
}
else {
echo "Нет пути из $origin в $destinationn";
}
}
}
Запустив этот пример мы получим следующее:
<?php
$g = new Graph($graph);
// минимальное число шагов из D в C
$g->breadthFirstSearch('D', 'C');
// вывод:
// из D в C за 3 шага
// D->E->F->C
// минимальное число шагов из B в F
$g->breadthFirstSearch('B', 'F');
// вывод:
// из B в F за 2 шага
// B->A->F
// минимальное число шагов из A в C
$g->breadthFirstSearch('A', 'C');
// вывод:
// из A в C за 2 шага
// A->F->C
// минимальное число шагов из A в G
$g->breadthFirstSearch('A', 'G');
// вывод:
// Пути из A в G нет
Если бы мы использовали стек вместо очереди, то обход стал бы в глубину.
Поиск оптимального пути
Другая распространенная проблема это поиск оптимального пути между двумя любыми узлами. Чуть раньше я уже говорил про построение маршрута в GoogleMaps как пример решения этой задачи. Как вариант, данную задачу можно применить к маршрутизации, управлению дорожным трафиком и так далее.
Один из знаменитых алгоритмов, направленных на решение данной проблемы был придуман в 1959 году 29-летним ученым по имени Эдсгер Вибе Дейкстра. Узнать подробнее про алгоритм можно в википедии или посмотреть на него в хабрапосте от splitface. В общих же чертах, решение Дейкстры сводится к проверке каждой связи между всеми возможными парами узлов, начиная от стартового узла, и поддерживая обновленным набор узлов с кратчайшей дистанцией, пока целевой узел не будет достигнут, если это возможно.
Есть несколько способов реализации данного решения, а также их дополнения. Некоторые из них улучшали производительность, а другие лишь указывали на недостатки решения Дейкстры, поскольку оно работает только с положительно взвешенными графами — такими, где нет отрицательных весов у связей.
Для примера возьмем следующий положительный граф и представим его через список, где укажем связи узлов между собой:
<?php
$graph = array(
'A' => array('B' => 3, 'D' => 3, 'F' => 6),
'B' => array('A' => 3, 'D' => 1, 'E' => 3),
'C' => array('E' => 2, 'F' => 3),
'D' => array('A' => 3, 'B' => 1, 'E' => 1, 'F' => 2),
'E' => array('B' => 3, 'C' => 2, 'D' => 1, 'F' => 5),
'F' => array('A' => 6, 'C' => 3, 'D' => 2, 'E' => 5),
);
Реализуем алгоритм с использованием приоритетной очереди для создания списка всех «неоптимизированных» узлов:
<?php
class Dijkstra
{
protected $graph;
public function __construct($graph) {
$this->graph = $graph;
}
public function shortestPath($source, $target) {
// массив кратчайших путей к каждому узлу
$d = array();
// массив "предшественников" для каждого узла
$pi = array();
// очередь всех неоптимизированных узлов
$Q = new SplPriorityQueue();
foreach ($this->graph as $v => $adj) {
$d[$v] = INF; // устанавливаем изначальные расстояния как бесконечность
$pi[$v] = null; // никаких узлов позади нет
foreach ($adj as $w => $cost) {
// воспользуемся ценой связи как приоритетом
$Q->insert($w, $cost);
}
}
// начальная дистанция на стартовом узле - 0
$d[$source] = 0;
while (!$Q->isEmpty()) {
// извлечем минимальную цену
$u = $Q->extract();
if (!empty($this->graph[$u])) {
// пройдемся по всем соседним узлам
foreach ($this->graph[$u] as $v => $cost) {
// установим новую длину пути для соседнего узла
$alt = $d[$u] + $cost;
// если он оказался короче
if ($alt < $d[$v]) {
$d[$v] = $alt; // update minimum length to vertex установим как минимальное расстояние до этого узла
$pi[$v] = $u; // добавим соседа как предшествующий этому узла
}
}
}
}
// теперь мы можем найти минимальный путь
// используя обратный проход
$S = new SplStack(); // кратчайший путь как стек
$u = $target;
$dist = 0;
// проход от целевого узла до стартового
while (isset($pi[$u]) && $pi[$u]) {
$S->push($u);
$dist += $this->graph[$u][$pi[$u]]; // добавим дистанцию для предшествующих
$u = $pi[$u];
}
// стек будет пустой, если нет пути назад
if ($S->isEmpty()) {
echo "Нет пути из $source в $targetn";
}
else {
// добавим стартовый узел и покажем весь путь
// в обратном (LIFO) порядке
$S->push($source);
echo "$dist:";
$sep = '';
foreach ($S as $v) {
echo $sep, $v;
$sep = '->';
}
echo "n";
}
}
}
Можно заметить, что решение Дейкстры — простой вариант поиска в ширину. Вернемся к примеру и опробуем его:
<?php
$g = new Dijkstra($graph);
$g->shortestPath('D', 'C'); // 3:D->E->C
$g->shortestPath('C', 'A'); // 6:C->E->D->A
$g->shortestPath('B', 'F'); // 3:B->D->F
$g->shortestPath('F', 'A'); // 5:F->D->A
$g->shortestPath('A', 'G'); // Нет пути из A в G
Все. На этом, судя по всему, статьи от Ignatius Teo по структурам закончились. Благодарю всех прочитавших, не ожидал, что первую часть так много человек поместит в избранное, хотя все мы знаем что избранное редко когда читается и все посты остаются там навсегда :)
Как обычно, в личку принимаются мои ошибки в тексте, переводе, противоречивая информация, а также наглое вранье.
В комментариях приветствуются обсуждение и последующие дополнения, чтобы добавить в статью.
Автор: yTko
