# HG changeset patch
# User Franz Glasner <fzglas.hg@dom66.de>
# Date 1729944587 -7200
# Node ID aead7cf1cb9a8c1471ea7cc3dd70404be72459e6
# Parent  e6af933f475e072013dfbac6a9e485fc3a744bd9
farray.sh: Extensive comment on index computation for heaps and variable usage for Heapsort

diff -r e6af933f475e -r aead7cf1cb9a share/local-bsdtools/farray.sh
--- a/share/local-bsdtools/farray.sh	Sat Oct 26 13:56:06 2024 +0200
+++ b/share/local-bsdtools/farray.sh	Sat Oct 26 14:09:47 2024 +0200
@@ -1800,6 +1800,34 @@
 #: See Also:
 #:   `_farr_array_heapsort`
 #:
+#: Note:
+#:   The heap is an implicit data structure which takes no space beyond the
+#:   array of objects to be sorted; the array is interpreted as a complete
+#:   binary tree where each array element is a node and each node's parent
+#:   and child links are defined by simple arithmetic on the array indexes.
+#:
+#:   The computation of these indexes is as follows:
+#:
+#:   - For 0-based indexes::
+#:
+#:       iLeftChild(i)  = 2⋅i + 1
+#:       iRightChild(i) = 2⋅i + 2
+#:       iParent(i)     = floor((i−1) / 2)
+#:
+#:   -  For 1 based indexes (in shell expession syntax and semantics)::
+#:
+#:       iLeftChild(i)  = 2 * i
+#:       iRightChild(i) = 2 * i + 1
+#:       iParent(i)     = i / 2
+#:
+#:   Variables:
+#:
+#:     Two variables (here, `start` and `end`) keep track of the bounds of the
+#:     heap area. The portion of the array before `start` is unsorted, while
+#:     the portion beginning at `end` is sorted. Heap construction decreases
+#:     `start` until it is one, after which heap extraction decreases `end`
+#:     until it is 2 and the array is entirely sorted.
+#:
 farray_heapsort() {
     local __farr_name