Нахождение k-го по величине элемента с помощью min-heap

У меня вопрос о поиске k-го по величине элемента с помощью min-heap. Алгоритм следующий:

  1. Берем первые k элементов и строим minheap

  2. Пусть Sk - наименьший элемент в S.

  3. Посмотрите на новый элемент из оставшихся n-k элементов.

  4. Если новый элемент больше Sk, он заменяет его в S и меняет порядок кучи.

  5. Тогда у S будет новый наименьший элемент.

  6. Посмотрев на все остальные элементы, Sk - ответ

Я не понимаю этого алгоритма. Например, пусть числа будут 1, 2, 3, 4. Мы хотим найти 4-й по величине, то есть 4. Но когда мы используем алгоритм, мы берем первые 4 элемента, строим мини-кучу, и Sk равно 1.

Что я делаю неправильно? Буду признателен, если кто-нибудь может помочь. Спасибо


sorting algorithm data-structures heap min-heap
person Community    schedule 12.01.2013    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Я думаю, что вы запутались в терминологии. Самый большой элемент в последовательности 1, 2, 3, 4 - это число 4. Второй по величине элемент - 3, третий по величине - 2, а четвертый по величине - 1. Поскольку алгоритм возвращает 1, он работает правильно. .

Однако 4 - это k-й- наименьший элемент в последовательности. Если вы хотите найти наименьший k-й элемент, вы можете просто поменять местами min-heap на max-heap и внести соответствующие изменения в алгоритм.

Надеюсь это поможет!

person templatetypedef    schedule 12.01.2013
comment
о, да, я думаю, что мой мозг на время перестал работать, это такая глупая ошибка. Спасибо! - person ; 13.01.2013
comment
@ user1941394 - Не беспокойтесь! Я потратил около пяти минут, пытаясь понять, в чем дело, так что я думаю, что это довольно простая ошибка. - person templatetypedef; 13.01.2013