Binary heap: Difference between revisions

Revision as of 20:35, 27 April 2024

Revision as of 20:39, 27 April 2024

Line 262:

In an array-based heap, the children and parent of a node can be located via simple arithmetic on the node's index. This section derives the relevant equations for heaps with their root at index 0, with additional notes on heaps with their root at index 1.

To avoid confusion, we'll define the '''level''' of a node as its distance from the root, such that the root itself occupies level 0.

=== Child nodes ===

Line 289:

\end{alignat}

</math>

As required.

Noting that the left child of any node is always 1 place before its right child, we get <math>\text{left} = 2i + 1</math>.

Line 298 ⟶ 296:

=== Parent node ===

Every non-root node is either the left or right child of its parent, so we know that eitherone of the following ismust true.hold:

#* <math>i = 2 \times (\text{parent}) + 1</math>

#* <math>i = 2 \times (\text{parent}) + 2</math>

Hence,