Самая быстрая структура данных для вставки / сортировка

Мне нужна структура данных, которая может вставлять элементы и сортировать себя как можно быстрее. Я буду вставлять намного больше, чем сортировка. Удаление - не большая проблема, и нет места. Моя конкретная реализация будет дополнительно хранить узлы в массиве, поэтому поиск будет O (1), т.е. вам не нужно об этом беспокоиться.