Структуры данных, PHP. Часть вторая

[amstr1k]

grrow.me/ пример работы с графами

[yTko]

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

[amstr1k]

Это всего лишь пример, пусть не самый наглядный

[yTko]

Я понимаю, он даже может и наглядный, но о сказав, что grrow строит графы на основе тех, кто лайкает статью, мало кто и что поймет. Сказав гуглокарты и построение маршрута — сразу понятно о чем речь :)

[tvolf]

Появился вот такой вопрос. Понимаю, что он, наверное, все же должен быть обращен к автору, но тем не менее ) Итак. Вот фрагмент кода из функции insert() вставки в кучу:

  $this->heap[] = $item;
  $place = $this->count();
  $parent = floor($place / 2);

Метод count() возвращает нам количество элементов в массиве heap, уменьшенное на 1. То есть, если элементов 5, то возвратит 4. Если 6 — то 5. И т.д.То есть, индекс последнего добавленного элемента равен
количеству элементов, уменьшенному на 1. Работает механизм индексации с нуля.
Parent — это индекс родительского элемента для нашего последнего вставленного элемента.

Так вот проблема в том, что при индексации массива с 0 (как у автора), а не с 1, вычисление индекса родителя просто целочисленным делением пополам будет давать неверные результаты.
Например, имеем вот такое дерево:

             A
           /   \
         B      C
        /  \
      D     E

В массиве это будет выглядеть так:

$heap = array(A, B, C, D, E);

Индекс последнего элемента (E) равен 4, если считать от нуля. Таким образом, по формуле выше, индекс родительского элемента для «E» должен быть равен 2 ( от «4 / 2»). То есть, «С» — родитель для «E». Что не есть верно. Если же индексация элементов была бы с единицы, то формула бы работала.

[yTko]

Да, я понял о чем вы. Начал было объяснять ситуацию тем, что в данном случае элемент так или иначе поднимается вверх и нет какого-то порядка, в котором вставляются новые элементы, но понял, что в итоге прихожу к вашей же ситуации :)
Здесь, думаю, проблема решает тем, что мы сначала должны вычислить place и parent, а затем вставить элемент в массив, т.е. place будет 3, а деление как раз выдаст индекс элемента B.

[akalend]

статья конечно хорошая, но применение графов не для РНР.

[yTko]

ну а язык-то тут причем? :) давайте не будем превращать комментарии в очередной спор о том, что php — зло, поскольку задачу нужно решать так, как это удобно и если мне будет удобнее решить ее на PHP, я воспользуюсь именно им.

[akalend]

Теоретически, конечно язык не причем. Лучше знаем РНР, значить лучше понимаем алгоритмы именно на этом языке. В этом смысле статья безупречная.
Что я хотел сказать — то именно практическое внедрение на РНР меня не устраивает. Прикладное использование графов требует русурсоемкости, и если это реализовывать на РНР, то это либо должен быть тяжелый и долгий бэкграунд, либо просто будет вылетать по таймауту или памяти.

Я понимаю, что минусуют те, кто с графами и расписаниями не имел дело.

[darkrain]

Слово куча упоминается 41 раз, я не удержался.



А за статью огромное спасибо! Мне для работы сейчас очень кстати

[yTko]

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

[darkrain]

Да все нормально. я читал статью с улыбкой

[Anisotropic]

Если уж статья для новичков, то расскажите зачем вообще нужна куча. Если в универе всякие задачи коммивояжера и симплекс-метод вдоль и поперёк исползали, то вот кучу я в принципе не припомню.

[yTko]

Возможно, вы правы, но чем пример с приоритетной очередью не устроил?
Это, по сути, немного измененная куча, где порядок вытаскивания элементов зависит не от расположения элемента в куче, а от параметра (приоритет)

[Anisotropic]

Тем что совсем не очевиден, как для новичка)

[yTko]

Если честно, данный материал я записал как «для новичков» по непонятной мне причине. на phpmaster они были в средней категории (не помню сейчас как она называлась, но для новичков была другая категория).
Не знаю, если бы мне сказали, что SplPriorityQueue это некий подтип кучи, то я бы в голове себе кучу всяких систем напридумывал. начиная от каких-нибудь примитивных баг-трекеров с приоритетом и напоминалками, и заканчивая какими-нибудь штуками для cron, когда тот, имея у себя несколько разных очередей (или одну большую), в определенном порядке бы выполнял что-то.
все упирается в воображение и ЯП, но это уже совсем другая история :)

[Anisotropic]

Я изначально про кучу спрашивал, а не про SplPriorityQueue. Про то дерево, где значение каждого потомка всегда меньше значения родителя.
>если бы мне сказали, что SplPriorityQueue это некий подтип кучи, то я бы в голове себе кучу всяких систем напридумывал
Логично, что человеку не знакомому с такими штуками ничего по аналогии в голову и не прийдёт? Я вот и спрашиваю это где-то реально используется, или просто умозрительный метод?

[yTko]

ну так в статье же сказано, что SplPriorityQueue реализована как куча, в чем проблема?
сама же куча, это практически отсортированное дерево (maxheap и minheap) и в любой момент времени можно получить максимальный или минимальный элемент.
википедия тоже говорит, что куча используется в разных алгоритмах и сортировках, что тоже довольно трудно понять новичку, поэтому вариант через приоритетную очередь, имхо, более понятен.