Здравствуйте, MTD, Вы писали:

MTD>Здравствуйте, sdf, Вы писали:

sdf>>Ну например, задача поиска первых минимальных N чисел (т.е., тех, что после сортировки будут идти первыми) в большом несортированом массиве. за O(длины массива) без N проходов по массиву. N << длины массива, массив можно модифицировать.

MTD>В смысле сделать из массива кучу?
Можно и сделать кучу, но это — перелопачивание всего массива. Модифицированный quicksort трогает только часть элментов и более эффективен с точки зрения локальности и кеша.

> Сдается мне пример крайне неудачный
Вполне удачый, вариант с хипом менее эффективный за счет того, что менее эффективно работает к кешем (менее локальный).