6. Что такое очередь? Как она устроена? Какие операции в ней есть?

О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел». Добавление элемента возможно лишь в конец очереди, выборка — только из начала очереди, при этом выбранный элемент из очереди удаляется.

7. Что такое куча (пирамида, Heap)?

Двои́чная ку́ча, пирами́да — такое двоичное дерево, для которого выполнены три условия:

Значение в любой вершине не меньше, чем значения её потомков.

Каждый лист имеет расстояние до корня либо d либо d-1. Иными словами, если назвать слоем совокупность вершин, находящихся на определённой глубине, то все слои, кроме, быть может, последнего, заполнены полностью.

Последний слой заполняется слева направо.

_______________________________________________________________________________

8. Какова стоимость операций с кучей?

Над кучей можно выполнять следующие операции:

• Добавить элемент в кучу. Сложность O(logn)

• Исключить максимальный элемент из кучи. Время работы O(logn)

• Изменить значение любого элемента. Время работы O(logn)

_______________________________________________________________________________

9. Как устроена очередь с приоритетами?

Очередь с приоритетом — абстрактный тип данных в программировании поддерживающий три операции:

• Добавить в очередь элемент с нaзначенным приоритетом

• Извлечь из очереди и вернуть элемент с минимальным приоритетом

• (необязательная операция) Просмотреть элемент с наивысшим приоритетом без извлечения

_______________________________________________________________________________

10. Какова стоимость операций в очереди с приоритетами?

O ( log n )

Вопросы

1. Быстрая сортировка

• Базовый алгоритм

Стратегия «разделяй и властвуй». Шаги алгоритма таковы:

1. Выбираем в массиве опорный элемент. Для повышения эффективности алгоритма выбираться должна медиана. Известные стратегии: выбирать постоянно один и тот же элемент; выбирать элемент со случайным индексом.

2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа . Обычный алгоритм операции:

• Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.

• Вычисляется индекс опорного элемента m.

• Индекс l последовательно увеличивается до m до тех пор, пока l-й элемент не превысит опорный.

• Индекс r последовательно уменьшается до m до тех пор, пока r-й элемент не окажется меньше либо равен опорному.

• Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.

• Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.

  3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

  4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

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

• Оцените сложность алгоритма в среднем и худшем случае

В среднем – n log n В худшем случае – n² Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.

• Какие оптимизации алгоритма существуют?

• При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — O(n log n).

• Выбирать опорным элементом средний из трех (первого, среднего и последнего элементов). Такой выбор также направлен против худшего случая.

• Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит log²n, а в худшем случае вырожденного разделения она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии.

• Разбивать массив не на две, а на три части

• Сортировка вставками

O(n²)

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно элементы вставляются по порядку их появления во входном массиве.

________________________________________________________________________________________