Cormen's heap sort structure

Question

I am going through heap sort chapter of the Cormen's algorithm book but got stuck in understanding below statements:

On most computers, the LEFT procedure can compute 2i in one instruction by simply shifting the binary representation of i left by one bit position.

Similarly, the RIGHT 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. The PARENT procedure can compute [i/2] by shifting i right one bit position. Good implementations of heapsort often implement these procedures as “macros” or “inline” procedures.

What is the LEFT procedure here, and how the calculation is done.

Similarly how it is calculated for RIGHT procedure & PARENT.

What it means that the procedures are implemented using macros or inline procedures.

From so many people I came to know this is the best book to learn algorithms but I am not able understand what the author is trying to explain here.

Answer 1

if you look at the binary representation of Node #2 it is 0000 0010 (i split after 4 bits for readability). A left-shift means that all bits take the place ofthe bits to the left of them and every bit who doesnt have a right neigbor will get a 0.

So, for example 0000 0001 will get 0000 0010 and your Node #2 will be 0000 0100. Did you see that the most right bit is now a zero? Also the binary representation 0000 0100 is 4, the exact same number the left child of the Node #2 had.

If you understand that, the rest is easy. A left shift with +1 would change 0000 0010 (2) to 0000 0101 (5). So this is the node-number of the right child.

A little bit trickier is the parent, because you will cut out something from the representation. If you want to get the parent of Node #3 0000 0011 you will shift right once so it becomes 0000 0001, which is 1. This works with both children as the most right bit will be cut off.

Now to macros & inline. Inline is a method in some programming languages (e.g. i learned it in c++) which tells a compiler he should evaluate if he could kind of speed up the given task. This is mostly useful for very simple task which also occur often (as your left&right shift tasks are). This makes sense, since such basic algorithms have to be very efficient since the more nodes you have to process the faster it will be slow. Macros are pretty much the same, just a save of a task which will be executed many times.

Some phrases you can google to understand better: Left-Shift bit operation Inline-Method c++

best wishes,

Essi

Answer 2

The parent, left, and right procedures are simple calculations to get the parent, left, and right elements, given a current element (at i).

Parent is the floor of i / 2

Left is 2i

Right is 2i + 1

---

Consider your provided example. Generally arrays are 0 based, but your example seems to be 1 based.

We have an array, call it A, where A = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1].

Let's say we are looking at A[3] which is 10. Using the above calculations, A[3]'s parent is A[1] which is 16. A[3]'s left child is A[6] which is 9. A[3]'s right child is A[7] which is 3.

---

On most computers, the LEFT procedure can compute 2i in one instruction by simply shifting the binary representation of i left by one bit position.

Similarly, the RIGHT 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. The PARENT procedure can compute [i/2] by shifting i right one bit position. Good implementations of heapsort often implement these procedures as “macros” or “inline” procedures.

This is describing the complexity of these functions at the processor level. The gist is that parent, left, and right can usually be executed in one or two instructions on the processor.

The comment on inline procedures is describing a compiler optimization. Compilers usually generate more assembly instructions than a human would if they wrote the assembly code themselves. So this comment is just saying that the (parent, left, and right) procedures can be compiled to single (or a couple) instructions, assuming the right compiler optimizations are available.

You can read about bit shifting (or read the other answer) if you are trying to understand how these procedures are actually run at the processor level.