Задача top-k-problem
Дан массив из n элементов требуется найти k наименьших(наибольших). Эквивалентно выдачи первых k элементов после сортировки. Это задача достаточно популярна в наши дни. Представьте поисковик google, который выдает результаты поиска по какому — то запросу. Как она работает? У него есть много много ссылок в памяти, и каждой ссылке в зависимости от ее релевантности по определенному запросу соответствует некое число, которое показывает рейтинг данной ссылки. Конечно google не хочет сортировать миллионы миллионы ссылок, чтобы выдать вам 20 — 1000 лучших ссылок, ему проще поддерживать некоторую кучу, в которой у нeго будут храниться эти наилучшие ссылки. Рассмотрим алгоритм нахождения k наилучших результатов(topk_problem)
- будем обрабатывать элементы по 1, слева направо по принципу потока
- h — пустая куча
- если просматривая элемент размер кучи меньше k, то добавим элемент в кучу
- если просматривая элемент размер кучи больше или равен k, то если элемент больше или равен вершины кучу, то пропускать, иначе добавлять его в вершину и вызывать heapify(0)
Этот алгоритм на каждом шаге поддерживает в куче наименьших k элементов. Алгоритм работает за , использую
дополнительной памяти.