Все Цель двоичной кучи

Определение:

очередиприоритетом является абстрактным типом данных, который подобен регулярной очереди или стека структуру данных, но где, кроме того, каждый элемент имеет «приоритет», связанный с ним , В очереди приоритетов элемент с высоким приоритетом обслуживается перед элементом с низким приоритетом. Если два элемента имеют одинаковый приоритет, они обслуживаются в соответствии с их порядком в очереди.Все Цель двоичной кучи

Реализация:

Для реализации очереди Приоритет, несортированный массив, отсортированный массив и двоичная куча структуры данных являются 3 стратегии осуществления.

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

или

каждый ключом как бинарного узел, имеющие два детей ,

Вопрос:

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

источник

2017-01-04 overexchange

См. Также раздел кучи. –

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

1. Просьба указать правильную атрибуцию источника, в котором вы скопировали это. См. Http://stackoverflow.com/help/referencing. 2. Запрос списка всех приложений двоичных куч, вероятно, слишком широк. 3. Какие исследования вы сделали? Вы смотрели в учебниках по структурам данных, чтобы посмотреть, что они делают с кучей? –

Бинарная куча может использоваться для извлечения (max или min) элемента в O (logn) времени. Это свойство может быть использовано для использования во многих алгоритмах, чтобы улучшить время выполнения.

Например, когда я использовал его в алгоритме сортировки k-merge, чтобы увеличить эффективность времени этапа сортировки сортировки k-merge. Короче говоря, он сделал двоичные кучи k-подмассивов, и сортировка может быть достигнута в линейном времени, которое лучше, чем обычный этап сортировки сортировки слияния.

Он также используется в алгоритме Дейкстры, алгоритме Прима, чтобы уменьшить время выполнения.

Вы также можете посмотреть here

источник

2017-01-04 09:58:27 CODError

Вы не можете извлекать элементы из двоичной кучи в постоянное время. * delete-min * - операция O (log n). Кроме того, ОП попросил использовать двоичную кучу, кроме как реализовать приоритетную очередь. Все три примера (сортировка слияния, алгоритм Дейкстры, алгоритм Прима) основаны на очередях приоритетов. Двоичная куча - просто удобная реализация. –

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

"extract (max или min) element" - это фактически определение очереди приоритетов, поэтому вы не ответили на вопрос, как отметил @JimMischel. \t «Если у вас есть ситуация, когда вы не используете двоичную кучу в качестве очереди приоритета», вы имеете ее обратно. Существует несколько способов реализации очередей приоритетов без использования кучи ... OP упоминает отсортированные и несортированные массивы, и есть множество других. Вопрос в том, хороши ли бинарные кучи ни для чего другого. См. Мой ответ для ... фактического ответа. Редактировать: Я думаю, может быть, у вас не было назад, просто плохо сформулировано. –

Бинарные отвалы имеют одну и другую полезную (и основной) применение: пирамидальная сортировка. HeapSort имеет более высокие накладные расходы, чем QuickSort, но его худшим случаем является O (n log n) и OS (n * n) QuickSort. QuickSort можно улучшить, чтобы получить наихудший случай O (n log n), переключившись на HeapSort, как только интервал будет достаточно коротким - это называется IntroSort, и это то, что используется в стандартной библиотеке STL и C++. См. https://en.wikipedia.org/wiki/Introsort

источник

2017-01-05 08:42:33

Определение:

Реализация:

ответ

Смежные вопросы