Как оптимизировать выборку с одновременной сортировкой?
=========================================================

 Есть большое множество элементов (в оперативной памяти), каждый из которых имеет некоторый набор тегов и вес (число, критерий для сортировки). Нужно сначала выбрать все элементы по 2-3 тегам, а потом из результата выбрать 10 штук с наибольшим весом.  
  

С тегами вроде всё просто - это хеширование. Если раскидать ссылки на элементы по хеш-таблицам, то можно почти за O(1) выбрать все нужные. Но потом в любом случае придётся сортировать. Можно ли как-то оптимизировать эту сортировку или избавиться от неё? Потому что на счету каждая микросекунда. 

 В общем, оказалось, что существенно ускорить алгоритм можно, если хоть капельку известна природа исходных данных.  
* Если известно распределение и границы, то почти точно вычисляем порог, выше которого будут наши 10 элементов. Раскладываем массив на две части (выше порога и ниже порога) за O(N). Даже если набрали 11-12 элементов больше порога, то за O(мало) уже смело сортируем и находим 10.
* Если распределение не известно, но известны границы (то есть минимум и максимум), то делаем предположение, что распределение равномерное, после чего вычисляем порог и задача сводится к предыдущему пункту.
* Если границы не известны, то за O(N) вычисляем минимум и максимум, после чего задача сводится к предыдущему пункту.

  

Конечно, всегда можно специально подсунуть такие данные, что алгоритм будет не эффективен. Но противодействие такому за рамками вопроса. 

[Куча/heap](https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D1%87%D0%B0_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)). Стройте кучу длиной 10 штук, пока выбираете. Куча может быть очень эффективно представлена массивом, имеет качественные реализации на почти всех языках. Ваша задача - академический пример применения кучи.