8.5 Упражнения¶
8.5.1 Вопросы для самопроверки¶
1. Как перестраивается куча после добавления числа 10¶
Массив [9, 7, 8, 3, 5] представляет максимальную кучу. Теперь в нее добавляют число 10.
- Сначала число 10 добавляется в конец массива. Чему равно значение его родительского узла?
- Выполните упорядочивание кучи снизу вверх, начиная с нового узла, и запишите массив после каждого обмена.
- Какой элемент в итоге окажется на вершине кучи? Сколько всего обменов выполнено?
Ответ
-
После добавления 10 его индекс равен 5, а индекс родительского узла равен \(\lfloor(5-1)/2\rfloor=2\). Значение родительского узла — 8.
-
Число 10 больше 8, поэтому после первого обмена получается
[9, 7, 10, 3, 5, 8]; затем 10 больше родительского узла 9, и после второго обмена получается[10, 7, 9, 3, 5, 8]. Число 10 достигло корневого узла, поэтому упорядочивание завершено. -
В итоге на вершине кучи находится 10. Всего выполнено 2 обмена.
2. Проверка отношений между родительскими и дочерними узлами минимальной кучи¶
Массив [1, 4, 3, 7, 6, 2] представляет полное двоичное дерево. В минимальной куче значение каждого родительского узла не превышает значения его дочерних узлов.
Для индекса \(i\) индексы левого и правого дочерних узлов равны \(2i+1\) и \(2i+2\) соответственно.
- Укажите индексы и значения дочерних узлов для индекса 2.
- В узле с индексом 2 находится значение 3. Нарушается ли правило минимальной кучи при сравнении этого узла с его дочерним узлом? Если да, какие элементы нужно поменять местами?
- С учетом ответа на вопрос 2: если правило нарушено, запишите массив после обмена; если не нарушено, объясните, почему обмен не требуется. Затем проверьте остальные отношения между родительскими и дочерними узлами.
Ответ
-
Левый дочерний узел индекса 2 имеет индекс 5 и значение 2. Индекс правого дочернего узла равен 6, но длина массива равна 6, поэтому такого узла нет.
-
Значение родительского узла 3 больше значения дочернего узла 2, что нарушает правило минимальной кучи. Нужно поменять местами элементы с индексами 2 и 5.
-
После обмена получается
[1, 4, 2, 7, 6, 3]. Проверим все отношения:1 ≤ 4,1 ≤ 2;4 ≤ 7,4 ≤ 6;2 ≤ 3. Каждый родительский узел теперь не больше своих дочерних узлов, поэтому правило минимальной кучи выполняется.
3. Сохранение трех наибольших чисел в минимальной куче¶
Чтобы сохранять 3 наибольших числа из потока данных [4, 1, 7, 3, 8], можно поддерживать минимальную кучу размером не более 3.
Сначала последовательно добавьте в минимальную кучу первые 3 числа. Когда куча заполнена, для каждого нового числа: если оно больше вершины кучи, удалите вершину и добавьте новое число; иначе оставьте кучу без изменений.
Запишите после чтения каждого числа набор чисел, хранящихся в куче, и ее вершину. Достаточно записывать сохраненные числа как множество; порядок их расположения в массиве кучи указывать не нужно.
Ответ
Результаты после чтения каждого числа:
| Прочитанное число | Сохраненные числа | Вершина кучи |
|---|---|---|
| 4 | {4} |
4 |
| 1 | {1, 4} |
1 |
| 7 | {1, 4, 7} |
1 |
| 3 | {3, 4, 7} |
3 |
| 8 | {4, 7, 8} |
4 |
После заполнения кучи на ее вершине находится наименьшее из сохраненных чисел. Новое число заменяет вершину,
только если оно больше нее. Итоговое множество {4, 7, 8} действительно содержит 3 наибольших числа.
8.5.2 Задачи по программированию¶
1. k-й наибольший элемент массива¶
Даны массив целых чисел nums и целое число \(k\), где \(1 \le k \le n\), а \(n\) — длина массива. Если расположить массив по убыванию, верните элемент на позиции \(k\).
Повторяющиеся элементы учитываются по отдельности. Например, 2-й наибольший элемент массива [5, 5, 2] по-прежнему равен 5. Используйте минимальную кучу размером не более \(k\).
Подсказки
- k-й наибольший элемент — наименьший среди k наибольших чисел
- Добавляйте каждое число в минимальную кучу, а когда ее размер превышает k, извлекайте наименьшее значение
- После обхода в куче останутся k наибольших чисел, а на ее вершине будет находиться ответ