title: How do I get the element with the smallest key in a collection, in O(1) or O(log n) time?
body: <p>I know that I can use a <code>Dictionary</code> and retrieve an arbitrary element in O(1) time.</p>
  
  <p>I know that I can get the next highest (or lowest) element in a <a href="http://msdn.microsoft.com/en-us/library/f7fta44c%28v=VS.90%29.aspx"><strong><code>SortedDictionary</code></strong></a> in O(1) time.  But what if I wanted to remove the <strong>first</strong> value (based on <code>TKey</code>'s <code>IComparable</code>) in the <code>SortedDictionary</code>?  </p>
  
  <p>Can I use the <a href="http://msdn.microsoft.com/en-us/library/bb291976%28v=VS.90%29.aspx"><strong><code>.First()</code></strong></a> method  to retrieve the smallest key?  And what is its complexity?  Will it run in O(1), O(log n) or O(n) time?</p>
  
  <p>Is the <code>SortedDictionary</code> the correct data structure for this?  </p>
  
  <p>Note: The use case is sort of a poor man's priority queue or ordered queue.  No open-source is allowed for this (must be code-from-scratch, or already in the .NET 3.5 framework).</p>