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

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

Этот алгоритм на каждом шаге поддерживает в куче наименьших k элементов. Алгоритм работает за , использую дополнительной памяти.

• Пирамидальная сортировка
• Heap Sort Реализация на С++
• Heap Sort Реализация на Java
• Понятие кучи и основные операции с ней