Блог

У меня есть вопрос в школе, что мне нужно найти k-й минимум элементов в минимальной куче. время выполнения, которое требовалось, составляет o(k^2), и я понял, как это сделать. но если я смогу свести это к o(k*logk), я получу бонус. я подумал о том, чтобы создать приоритетную очередь из минимальной кучи, а затем вставить узел кучи в очередь, а затем удалить его, затем проделать то же самое с дочерними элементами корня минимальной кучи и так далее k раз. я знаю, что временная сложность операций вставки и pop равна o(logk), поскольку начальный размер очереди приоритетов равен единице, и он увеличивается не более чем на единицу на каждом из k шагов. Таким образом, в очереди приоритетов содержится максимум k 1 элементов.

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

Спасибо

Да, ваша идея звучит неплохо. Я покажу, как это сделать на Python.

Сборка кучи из массива

Итак, сначала создайте минимальную кучу поверх вашего входного массива:

 def create_min_heap(array):
    min_heap = []
    for value in array:
        heappush(min_heap, value)

    return min_heap
 

Отсчитайте k минимальных элементов из кучи

Создайте вспомогательную минимальную кучу, которая будет использоваться для извлечения всех k минимальных элементов в O(klogk). На каждом шаге из него будет извлечен минимальный элемент, и 2 будут добавлены его дочерние узлы (дочерние элементы можно найти в исходной минимальной куче). Пожалуйста, обратите внимание, что нет смысла добавлять дочерние элементы других узлов в вспомогательную минимальную кучу, потому что они не могут быть меньше своих родителей (для каждого свойства кучи).

 def k_min_elements(min_heap, k):
    result = list()
    helper_min_heap = []
    heappush(helper_min_heap, (min_heap[0],0))
    while len(result) < k:
        min_node = heappop(helper_min_heap)
        value = min_node[0]
        index = min_node[1]

        left_index = index*2   1
        right_index = left_index   1
        if left_index < len(min_heap):
            heappush(helper_min_heap, (min_heap[left_index], left_index))
        if right_index < len(min_heap):
            heappush(helper_min_heap, (min_heap[right_index], right_index))

        result.append(value)

    return result 
 

Полный Код

Теперь полный код и пример вывода.

 from heapq import heappop
from heapq import heappush

def create_min_heap(array):
    min_heap = []
    for value in array:
        heappush(min_heap, value)

    return min_heap

def k_min_elements(min_heap, k):
    if k > len(min_heap) or k < 0:
        raise Exception("k is invalid")

    result = list()
    helper_min_heap = []
    heappush(helper_min_heap, (min_heap[0],0))
    while len(result) < k:
        min_node = heappop(helper_min_heap)
        value = min_node[0]
        index = min_node[1]

        left_index = index*2   1
        right_index = left_index   1
        if left_index < len(min_heap):
            heappush(helper_min_heap, (min_heap[left_index], left_index))
        if right_index < len(min_heap):
            heappush(helper_min_heap, (min_heap[right_index], right_index))

        result.append(value)

    return result


min_heap = create_min_heap([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print (k_min_elements(min_heap, 3))
 

[0, 1, 2]