Обсуждение:Очередь с приоритетом (программирование)

Предложение по улучшению

Статья пестрит названиями методов (которые каждый автор, видимо, волен выбирать — во всяком случае, я не нашёл никакой стандартизации), а суть остаётся размазанной. Предлагаю убрать все эти названия и заменить русскими обозначениями в традициях старых книг по программированию. Если нет возражений, начну редактирование в этом направлении. РоманСузи 15:34, 23 ноября 2014 (UTC)

Я не против. Но, если это будет сразу со сносками. ~Нирваньчик~ ^øβς 06:24, 24 ноября 2014 (UTC)

Ясное дело, по источникам. Без сносок в большинстве случаев, кроме тривиальных, означает удаление. Или что Вы имеете в виду под «со сносками»? РоманСузи 07:16, 24 ноября 2014 (UTC)

Да ничего такого. Просто, чтобы не было замены одного орисса на другой, чтоб по источнику писалось. Если есть классические наименования на русском, то это большая радость, надо стремиться к ним. А сноски это просто пожелание, чтобы утвердить тексты, так сказать "заморозить" их, "застолбить". ~Нирваньчик~ ^øβς 07:34, 24 ноября 2014 (UTC)

В том-то и проблема, что нет «классических» наименований ни на русском, ни на английском. Поэтому предложение состоит в том, чтобы перевести (по источнику) что-то удобочитаемое. Так как я сам несколько сомневаюсь в том, что это будет консенсусно, то спросил. Возможно, лучше в проекте спросить. Вопрос в том, требует ли русифицированный «псевдокод» и названия методов отдельных источников? Полагаю, что как только два источника называют что-то двумя разными способами, можно спокойно просто переводить. Скажем, метод pop у стека утвердился, а вот методы очереди с приоритетами по всей видимости нет. РоманСузи 07:51, 24 ноября 2014 (UTC)

Разбираемся

(это я что-то вроде черновика). Итак, русская версия была написана по английской, которая не очень чёткая. Ниже анализ трёх источников, из которых нужно выделить нечто общее:

• ОсП можно понимать упрощённо, как просто набор элементов, которые сами по себе ключи (так делает Robert Sedgewick and Kevin Wayne, но зачем это только нужно?). Операции называются insert и delMax
• Ахо и др. явно говорит что очередь — множество элементов, но элементом у него не числа, а например запись вроде process, у которого есть ид и приоритет. В самом начале же говорится о функции p, которая по элементу вычисляет приоритет (то есть, в простейшем случае берёт приоритет из поля приоритет). Названия операций: INSERT и DELETEMIN. Здесь же интересный пример про приёмный покой больницы.
• у Кормена и др. возможные операции: insert((k, v)), maximum() и extract_maximum(), где (k, v) — ключ, определяющий приоритет, и v — значение. Как и Ахо и др. он говорит, что очередь — множество.
• При этом есть два варианта ОсП — для минимума и максимума (delMin и delMax).
• Ахо и др. добавляет ещё одну операцию — MAKENULL — которая является конструктором. Robert Sedgewick and Kevin Wayne говорят о двух обязательных операциях, но «для полноты» добавляют еще ворох всяких.
• Наконец, в третьем томе Искусства программирования Кнут так ничего определённого не говорит, операции никак не называет. «наибольший из включённых первым исключается» — это видимо для сравнения с FIFO и LIFO. Дальше сразу разговор о реализациях на основе деревьев, зато в конце целый список различных вариантов реализации. И, кроме того, говорится, что всё пошло от статьи Williams 1964 года о heapsort и работ Crane, C.A.

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

В общем, похоже, самые удачные названия — insert и extract_min или как у Кормена и др. У него же несколько проще элемент — (k, v). РоманСузи 19:00, 24 ноября 2014 (UTC)

Мне нравится текущий вариант псевдокода, не смотря на смешивание латинских и кириллических ключевых слов. Я думаю, достаточно если названия операций встречаются в АИ, а уже выбирать из них неважно какое, раз у них нет общего варианта. Надо только разобраться с максимумом/минимумом. Во вводной части написано "извлечь максимум" а в Описании "extract_minimum()" - негармонично. Надо что-то одно выбрать. ~Нирваньчик~ ^øβς 14:32, 26 ноября 2014 (UTC)

Примеры

А другие есть примеры? На других языках, ато Python это такой специфичный язык, что я при чтении такого предпочитаю смотреть пример на С или C-подобном языке. ~Нирваньчик~ ^øβς 14:32, 26 ноября 2014 (UTC)

• Python краток и наиболее близок к псевдокоду. В данном случае пример не собственно реализации, а использования библиотеки. Другие примеры ищу. Если получится, должно быть что-то императивное (JavaScript) и хорошо бы функциональное (например, по книге Криса Окасаки). РоманСузи 18:01, 26 ноября 2014 (UTC)