При условии, что диапазон [first, last – 1) является кучей (см. алгоритм make_heap), добавляет в эту кучу элемент, расположенный в позиции last – 1, формируя тем самым кучу в диапазоне [first, last). Для сравнения элементов используется предикат comp(*p1, *p2) или (по умолчанию) операция <.
Сложность логарифмическая (не более log N сравнений).
Случайным образом изменяет порядок элементов из диапазона [first, last). Для генерации случайных чисел по умолчанию используется встроенный генератор с равномерным распределением; может также использоваться явно заданный генератор rand(n), возвращающий целое случайное число в диапазоне [0, n). В стандарте C++11 алгоритм random_shuffle объявлен устаревшим; вместо него рекомендуется использовать алгоритм shuffle.