Задача top-k-problem

Алгоритмы   13 Март 2012  Автор статьи:  

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

  1. будем обрабатывать элементы по 1, слева направо по принципу потока
  2. h — пустая куча
  3. если просматривая элемент размер кучи меньше k, то добавим элемент в кучу
  4. если просматривая элемент размер кучи больше или равен k, то если элемент больше или равен вершины кучу, то пропускать, иначе добавлять его в вершину и вызывать heapify(0)

Этот алгоритм на каждом шаге поддерживает в куче наименьших k элементов. Алгоритм работает за O(n\times\log{k}), использую O(k) дополнительной памяти.

Научиться программировать

  • на Delphi

  • на Java

  • на C++