title: What data structure is used to implement the dynamic memory allocation heap?
body: <p>I always assumed a <a href="http://en.wikipedia.org/wiki/Heap_%28data_structure%29" rel="noreferrer">heap (data structure)</a> is used to implement a <a href="http://en.wikipedia.org/wiki/Dynamic_memory_allocation#Dynamic_memory_allocation" rel="noreferrer">heap (dynamic memory allocation)</a>, but I've been told I'm wrong.</p>
  <p>How are heaps (for example, the one implemented by typical <code>malloc</code> routines, or by Windows's <code>HeapCreate</code>, etc.) implemented, typically? What data structures do they use?</p>
  <h3>What I'm <em>not</em> asking:</h3>
  <p>While searching online, I've seen <em><strong>tons</strong></em> of descriptions of how to implement heaps <em>with severe restrictions</em>.<br />
  To name a few, I've seen lots of descriptions of how to implement:</p>
  <ul>
  <li>Heaps that never release memory back to the OS (!)</li>
  <li>Heaps that only give reasonable performance on small, similarly-sized blocks</li>
  <li>Heaps that only give reasonable performance for large, contiguous blocks</li>
  <li>etc.</li>
  </ul>
  <p>And it's funny, they all avoid the harder question:<br />
  How are &quot;normal&quot;, general-purpose heaps (like the one behind <code>malloc</code>, <code>HeapCreate</code>) implemented?</p>
  <p>What data structures (and perhaps algorithms) do they use?</p>