title: Is partial-order, in contrast to total-order, enough to build a heap?
body: <p>C++ std::priority_queue just need a partial order. But if its implementation is a <strong>binary heap</strong>, how does it works?
  For example: assume we have a partially ordered set <code>( {a, b, c, x}, {c &lt; b, b &lt; a, c &lt; a} )</code>, <code>x</code> has nothing to do with <code>a</code>, <code>b</code>, <code>c</code>. Then a max-heap is:</p>
  
  <pre><code>layer 1:    x
  layer 2:  b   x
  layer 3: x x a c
  </code></pre>
  
  <p>After a pop operation, in a way commonly seen in text books, i.e. replace the root with <code>c</code> and decrease the size by 1. Then we need to heapify the tree below, at the root:</p>
  
  <pre><code>layer 1:    c
  layer 2:  b   x
  layer 3: x x a
  </code></pre>
  
  <p>We will swap <code>c</code> and <code>b</code> as <code>c &lt; b</code>, won't we? And what? We still don't have a valid heap since <code>b &lt; a</code>. But <code>b</code> cannot "see" <code>a</code>.</p>