Мне сложно понять, почему в решениях для поиска k-го наименьшего элемента используется подход с максимальной кучей. И для k-го по величине элемента подход минимальной кучи. Разве не имеет смысла использовать минимальную кучу для поиска k-го наименьшего элемента, поскольку наименьший элемент всегда будет корневым? Итак, если мы хотим найти 3-й наименьший элемент, мы просто удаляем корень 2 раза, строим кучу и получаем 3-й наименьший элемент. В максимальной куче самый маленький не находится в корне, так почему лучше использовать? То же самое касается сортировки по возрастанию или убыванию чисел в массиве. Я вижу, что большинство людей используют максимальную кучу для подъема.
Максимальная куча против минимальной кучи для k-го наименьшего элемента
Ответы (1)
Фактически, мы можем использовать как Min, так и Max heap, чтобы найти k-й наименьший элемент:
- Как вы описали, мы можем построить Min Heap, а затем извлечь k-й элемент в цикле.
or
- Мы можем построить Max Heap всего из k элементов. Затем мы просто сравниваем остальные элементы с корнем, заменяя корнем только те элементы, которые меньше корня, поэтому максимальная куча всегда имеет k наименьших элементов.
person
Andriy Berestovskyy
schedule
07.11.2018
Но как узнать, что вы находитесь на k-м наименьшем элементе? Разве вам не нужно было бы сравнивать все элементы в массиве до конца, прежде чем вы узнаете, является ли он k-м наименьшим?
- person ; 07.11.2018
@ mth1417 конечно, сначала вам нужно построить небольшую Max Heap с первыми k элементами, затем нам нужно сравнить остальную часть массива с Max Heap root. Но для создания Min Heap вам также необходимо сравнить все элементы массива. Кроме того, нам нужно извлечь k элементов, где k может быть размером с n ...
- person Andriy Berestovskyy; 07.11.2018
Зачем вам нужно сравнивать все элементы в минимальной куче, если самый маленький всегда находится в корне, вам просто нужно проверить root?
- person ; 07.11.2018
@ mth1417 нам нужно сравнить все элементы, чтобы построить Min Heap. Сложность создания кучи составляет O (n * log n), поэтому мы касаемся всех элементов, и для каждого элемента мы выполняем heapify, который равен O (log n). Для Max Heap мы делаем heapify только для k элементов, так что это O (k * log k), а затем мы просто сравниваем остальную часть массива с корнем Max Heap, иногда вызывая heapify только для k элементов. Таким образом, сложность для Max Heap составляет O (n * log k), а для Min Heap - O (n * log n) + O (k * log n) для извлечения k min элементов.
- person Andriy Berestovskyy; 07.11.2018
Извините, но я не понимаю, почему извлечение - это O (k * log n), когда извлечение всегда является только первым элементом
- person ; 07.11.2018
Еще один момент: с Max Heap мы можем мгновенно сохранить k наименьших элементов в онлайн-режиме - без полного массива.
- person MBo; 07.11.2018
@ mth1417 Извлечение вершины вызывает перестройку кучи за log (n) шагов. Извлечение k раз - klogn
- person MBo; 07.11.2018
@ mth1417 Потому что куча выглядит как двоичное дерево поиска, но на самом деле это не так. Каждый раз, когда мы вставляем / извлекаем элемент, куча должна быть скопирована, т.е. свойства кучи должны быть восстановлены. Сложность heapify составляет O (log n). Пожалуйста, загляните в Википедию для получения более подробной информации или добавьте еще один вопрос, если у вас остались вопросы: en.wikipedia. org / wiki / Binary_heap
- person Andriy Berestovskyy; 07.11.2018
Одно небольшое исправление: heapify, например. построение кучи из произвольного массива фактически занимает O (n) с использованием подхода sift / bubble down. Источник: stackoverflow.com/questions/9755721/ (это также отмечено в статье википедии о двоичной куче)
- person KhalilRavanna; 17.07.2020
@KhalilRavanna К сожалению,
heapify не является построением кучи из произвольного массива. Heapify - это процесс восстановления свойства кучи, и он занимает O (log n). Пожалуйста, прочтите внимательно ссылки, все они говорят одно и то же ...
- person Andriy Berestovskyy; 17.07.2020
Хм, я нахожу терминологию изобилующей во многих местах, включая статью в Википедии, в которой уточняется то, что я описал. Не здорово, что терминология кажется смешанной. Похоже, вы описали именно то, о чем говорите, в своем комментарии, поэтому, пожалуйста, извините за мои возражения. en.wikipedia.org/wiki/Heap_(data_structure)
- person KhalilRavanna; 19.07.2020
