Учитывая следующую проблему, я не совсем уверен в своем текущем решении:
Вопрос:
Учитывая максимальную кучу с элементами n, которая хранится в массиве A, можно ли распечатать все самые большие элементы K в O(K*log(K))?
Мой ответ:
Да, это так, поскольку для поиска элемента требуется O(log(K)), следовательно, это
для K элементов потребуется O(K * log(K)) время выполнения.
Это возможно в макс-куче, потому что вы только печатаете элементы из дерева, а не извлекаете их.
Начните с определения максимального элемента, который находится в корневом каталоге node. Создайте указатель на node и добавьте его в пустой список "максимум". Затем для каждого из значений k выполните следующие шаги в цикле.
В общем случае время выполнения - O (klog (k)), если требуется.
Поиск элемента в куче размера N не O (K). Во-первых, не имеет смысла, что временная сложность поиска одного элемента зависит от количества элементов, которые вы пытаетесь извлечь (что и представляет K). Кроме того, не существует такой вещи, как поиск в куче /mdash; если вы не подсчитаете стандартный поиск по каждому элементу в O (N).
Однако поиск самого большого элемента в куче - это O (1) по дизайну (я, очевидно, предполагаю, что это максимальная куча, поэтому максимальный элемент находится в верхней части кучи) и удаляет наибольший элемент из куча размера N равна O (log (N)) (замените его листовым элементом, и этот лист просачивается обратно вниз в кучу).
Итак, извлечение элементов K из кучи и возврат кучи неисследованных элементов приведет к времени O (K & middot; log (N)).
Что произойдет, если вы извлечете K-элементы без разрушения из кучи? Вы можете сделать это, сохранив кучу кучи (где значение кучи - это значение ее максимального элемента). Первоначально эта куча кучи содержит только один элемент (исходная куча). Чтобы извлечь следующий максимальный элемент, вы извлекаете верхнюю кучу, извлекаете ее верхний элемент (который является максимальным), а затем снова вставляете две подвалы обратно в кучу кучи.
Это увеличивает кучу кучи по одному при каждом удалении (удаляет один, добавляет два), что означает , он никогда не будет содержать больше элементов K, и поэтому remove-one-add -два возьмем O (log (K)). Итерации, и вы получите фактический алгоритм O (K & middot; log (K)), который возвращает верхние K-элементы, но не может вернуть кучу неисчерпаемых элементов.
Я нашел, что другие ответы смущали, поэтому я решил объяснить это с помощью фактической кучи примера. Предположим, что оригинальная куча - это размер N, и вы хотите найти k-ые элементы, Это решение занимает время O (klogk) и O (k).
10
/ \
5 3
/ \ /\
4 1 2 0
Original Heap, N = 7
Хотите найти 5-й по величине элемент. k = 5 Примечание. В новой куче вам нужно сохранить указатель на исходную кучу. Это означает, что вы не удаляете или не изменяете исходную кучу. Исходная куча доступна только для чтения. Поэтому вам никогда не придется выполнять какие-либо операции, для которых требуется время O (logN).
Пусть x '- указатель на значение x в исходной куче.
1st Iteration: получить root node указатель в новую кучу
Шаг 1: добавьте указатель на node 10
10'
New Heap, size = 1, root = 10', root->left = 5, root right->3
Распечатайте первый наибольший элемент = 10
2-я итерация. Обратитесь к исходной куче и вставьте ее в новую кучу. (Хранение указателей на них, а не самих значений). Причина, по которой вы хотите сохранить указатель, заключается в том, что вы можете получить к ним доступ в O (1) из исходной кучи позже, чтобы искать своих детей вместо O (N), чтобы найти, где это значение находится в исходной куче.
Шаг 2a: Найдите левого ребенка root node новой кучи из исходной кучи. Добавьте указатель для левого ребенка (в данном случае, 5 ') в новую кучу.
10'
/
5'
New Heap, size = 2, root = 10', root->left = 5, root right->3
Шаг 2b: Посмотрите на правильный дочерний корень node новой кучи из исходной кучи. Добавьте указатель для левого ребенка (в данном случае, 3 ') в новую кучу.
10'
/ \
5' 3'
New Heap, size = 3, root = 10', root->left = 5, root right->3
Шаг 2c: Удалите root node из новой кучи. (Swap max node с правом самого отпуска, удалите root node и смените текущий корень, чтобы сохранить свойство кучи)
10' swap 3' remove & bubble 5'
/ \ => / \ => /
5' 3' 5' 10' 3'
New Heap, size = 2, root = 5', root->left = 4, root right->1
Распечатайте второй наибольший элемент = 5
Шаг 3a: Найдите левого ребенка root node новой кучи из исходной кучи. Добавьте указатель для левого ребенка (в данном случае, 4 ') в новую кучу.
5'
/ \
3' 4'
New Heap, size = 3, root = 5', root->left = 4, root right->1
Шаг 3b: Посмотрите на правильный дочерний корень node новой кучи из исходной кучи. Добавьте указатель для левого ребенка (в данном случае, 1 ') в новую кучу.
5'
/ \
3' 4'
/
1'
New Heap, size = 4, root = 5', root->left = 4, root right->1
Шаг 3c: Удалите root node из новой кучи. (Swap max node (5 ') новой кучи с самым большим правом покинуть исходную кучу (1') из новой кучи, удалить корень node и свернуть текущий корень, чтобы сохранить свойство кучи)
5' Swap 1' remove & bubble 4'
/ \ => / \ => / \
3' 4' 3' 4' 3' 1'
/ /
1' 5'
New Heap, size = 3, root = 4', root->left = NULL, root right->NULL
Распечатайте третий по величине элемент = 4
Шаг 4a и шаг 4b ничего не предпринимают с тех пор, как root node не имеет детей в этом случае из исходной кучи.
Шаг 4c: Удалите корень node из новой кучи. (Swap max node с правом самого отпуска, удалите root node и опустите текущий корень, чтобы сохранить свойство кучи в новой куче)
4' Swap 1' remove & bubble 3'
/ \ => / \ => /
3' 1' 3' 4' 1'
New Heap, size = 2, root = 3', root->left = 2, root right->0
Распечатайте 4-й наибольший элемент = 3
Шаг 5a: Посмотрите на левый ребенок корня node новой кучи из исходной кучи. Добавьте указатель для левого ребенка (в данном случае, 2 ') в новую кучу.
3'
/ \
1' 2'
New Heap, size = 3, root = 3', root->left = 2, root right->0
Шаг 5b: Посмотрите на правильный дочерний корень node новой кучи из исходной кучи. Добавьте указатель для левого ребенка (в данном случае, 0 ') в новую кучу.
3'
/ \
1' 2'
/
0'
New Heap, size = 4, root = 3', root->left = 2, root right->0
Шаг 5c: Удалите корень node из новой кучи. (Swap max node (3 ') с его правом преимущественным удалением из исходной кучи (которая равна 0') в новой куче, удалите корень node и смените текущий корень, чтобы сохранить свойство кучи в новой куче)
3' Swap 0' Remove & Bubble 2'
/ \ => / \ => / \
1' 2' 1' 2' 1' 0'
/ /
0' 3'
New Heap, size = 3, root = 2', root->left = NULL, root->right = NULL
Печать 5-го по величине элемента = 2
Наконец, поскольку мы прошли через k итераций, k = 5. Теперь мы можем извлечь значение корневого элемента из новой кучи. В этом случае значение равно 2. Поэтому мы нашли k-е наибольшее значение из первоначальной кучи.
Сложность времени, T (N, k) = O (klogk) Космическая сложность, S (N, k) = O (k)
Надеюсь, это поможет!
Вскоре Chee Loong,
Университет Торонто.
Действительно, это слишком просто, извлечение максимального элемента O(log(N)), где N - размер кучи. и N≠K.
Я добавлю, что поиск случайного элемента O(N), а не O(log(N)), но в этом случае мы хотим извлечь max.
It is a simple and elegant algorithm to get first k elements of a max heap in k log(k) time.
steps:-
1.construct another max heap name it auxiliary heap
2.add root element of main heap to auxiliary heap
3.pop out the element from auxiliary heap and add it 2 children to the heap
4.do step 2 and 3 till k elements have been popped out from auxiliary heap. Add the popped element children to the auxiliary heap.