Требуется контейнер для типа KeyValuePair<Key, Value>
со следующими свойсвами
1) упорядоченность по key
2) быстрая вставка / удаление с сохранением сортированности
3) возможность итерации вперед и назад по KeyValuePair, как по упорядоченному списку.

стандартный SortedDictionary<key, value> соответсвует 1) и 2), но предоставляет лишь IEnumerator, который может идти только сначала и только вперед.
Согласно ТЗ требуется найти и извлечь максимум по key (но с некоторыми проверками по value) , а также n элементов, которые идут прежде ( с меньшими key). 
Все эти операции нужно делать в высшей степени оптимально,  так как предполагается обработка данных в реальном времени.


Похоже, тут понадобится что-то наподобие кучи(ради быстрой вставки), но вот вопрос - есть ли библиотеки алгоритмов и конейнеров для C# которые предоставляют реализацию кучи, и которые можно допилить до нужной кондиции?
 (GPL инфекция неприемлема)