Heap Bit-Shift Macros for Left, Right and Parent
<p>I am reading about Heaps, which describes that you can do the operations of accessing the left child, the <strong>RIGHT</strong>/<strong>LEFT</strong> child and the <strong>PARENT</strong> with bit shift operations. While Left and Parent seems trivial i am not sure with the right one. Do i just have to add one?</p>

<p>Here is an excerpt from the book: MIT Introduciton to algorithms:</p>

<p>"Similarly, the <strong>RIGHT</strong> procedure can quickly compute 2i + 1 by shifting the binary representation of i left by one bit position and then adding in a 1 as the low-order bit". </p>

<p><a href="http://i.stack.imgur.com/NSIYI.png" rel="nofollow"><img src="http://i.stack.imgur.com/NSIYI.png" alt="MIT Introduction to Algorithms - Heap"></a></p>

<p><strong>Access Operations:</strong></p>

<p>LEFT: 2*i</p>

<pre><code>i&lt;&lt;1
</code></pre>

<p>RIGHT: 2*i+1</p>

<pre><code>(i&lt;&lt;1)+1
</code></pre>

<p>PARENT: i/2</p>

<pre><code>i&gt;&gt;1
</code></pre>

<p>This is how heap works - for every node you could easily get:</p>

<ol>
<li>Parent - just divide the node index by two (<code>N / 2</code>)</li>
<li>Left child - multiply index by two (<code>N * 2</code>)</li>
<li>Right child - multiply index by two and increase new index by one (<code>N * 2 + 1</code>)</li>
</ol>

<p>It is easy to prove, that two distinct nodes cannot have same child. </p>

<p>Suppose, <code>N1</code>, <code>N2</code> and <code>C</code> are heap nodes. <code>N1 != N2</code> and <code>C.is_child_of(N1)</code> and <code>C.is_child_of(N2)</code>, where <code>C.is_child_of(N)</code> returns <code>true</code> when <code>C</code> is either right or left child of <code>N</code>. Then:</p>

<ol>
<li>If <code>C</code> is the left child of both <code>N1</code> and <code>N2</code>, then <code>N1 * 2 = N2 * 2 &lt;=&gt; N1 = N2</code></li>
<li>Similarly, if <code>C</code> is the right child of both <code>N1</code> and <code>N2</code>, then <code>N1 * 2 + 1 = N2 * 2 + 1 &lt;=&gt; N1 = N2</code></li>
<li>If <code>C</code> is the left child of <code>N1</code> and <code>C</code> is the right child of <code>N2</code>, then <code>N1 * 2 = N2 * 2 + 1</code> which is incorrect, because <code>N1 * 2</code> is even and <code>N2 * 2 + 1</code> is odd.</li>
</ol>

<hr>

<p>Note, that your bitwise access operations are incorrect - you should shift indices by one, not by two, because <code>N &lt;&lt; M</code> is <code>N * 2^M</code>. I'd also suggest you to use plain division / multiplication instead of bit shifting - the compiler knows how to optimize your code.</p>

python c++ algorithm heap