직접 구현한 MinHeap

C# 에는 heap 도 없고 set도 없다. multiset 도 없다.

그래서 이런것들을 구현해놓은 

http://powercollections.codeplex.com/

이런 위대한 분도 계신다.

나는 네트워크 엔진을 구현하다가

"거의 정렬된 순서로 들어오는 input 에 대해 add,remove 성능이 좋은 min-heap" 이 필요했는데,

SortedList<T> 나 SortedDictionary<T> 를 써봐도 성능이 도통 좋지 못했다.

위에서 언급한 power collection 을 써봐도 마찬가지였고 그래서 직접 구현했다.

테스트코드와 함께 업로드한다. 테스트 코드는 완벽하게 sorting 된 input을 집어넣는데,

모든 경우에 있어 내가 구현한 heap이 가장 성능이 좋음을 알 수 있다.

딱히 sorting된 input에 대해 최적화를 할 수 없었는데, random input에 대해서도 아마 성능이 꽤 괜찮을 것이다.

ConsoleApplication1.zip

MinHeap.cs