In Algorithms by Bob Sedgewick (https://www.coursera.org/learn/algorithms-part1/lecture/ZjoSM/heapsort) he constructs a heap using bottom up method, starting at index N/2. Why there? What is the meaning of this index for the heap sorted array?

CodePudding user response：

N/2 is the position of the last node (rightmost in the array) that still has children (at least one). The reason to start there is that all nodes that are to the right of that node (i.e. at positions N/2 1 and greater) are all leaves, and therefore do not need to be heapified.

CodePudding user response：

Let's consider a binary tree with levels numbered from 0. It has 2^0 nodes at the zeroth level, 2^1 at the first level, 2^2 nodes at the second level, and so on. In general, it has 2^K nodes at the Kth level.

The number of nodes from levels 0 through L-1 is equal to 2^0 2^1 2^2 ... 2^(L-1) = 2^L - 1. If the root has index 1, then the indices at level L are from 2^L through 2^(L 1) - 1. Dividing that range by 2 results in values from 2^(L-1) through 2^L - 1, which means the division maps the indices from level L to the indices from level L-1. Let's take a closer look at the first four nodes at level L: 2^L / 2 = 2^L 1 / 2 = 2^(L-1), 2^L 2 / 2 = 2^L 3 / 2 = 2^(L-1) 1. Generally, indices of children are mapped to indices of their parents. This shows why it's beneficial to store a binary tree in an array indexed from 1. It makes it easy to find parent indices. However, arrays are usually indexed from 0. In such cases, the cell at index 0 in the array can be left unused.

Because heap leaves satisfy the heap condition, they don't require any changes. The first node potentially requiring the sink operation when moving right-left and bottom-up is the last node's parent. As the last node has index N, the first analyzed node has index N/2.