Add documentation for equality-aware variants of min-heap maintenance
functions, which use a top-down sift_down strategy. These variants,
suffixed with _eqaware, reduce the number of comparisons to O(1) in
workloads with many elements of equal priority and can be used as
drop-in replacements for their standard counterparts.
Cc: stable@xxxxxxxxxxxxxxx # 6.11+
Signed-off-by: Kuan-Wei Chiu <visitorckw@xxxxxxxxx>
---
Documentation/core-api/min_heap.rst | 20 ++++++++++++++++++++
1 file changed, 20 insertions(+)
diff --git a/Documentation/core-api/min_heap.rst b/Documentation/core-api/min_heap.rst
index 9f57766581df..012c82038b46 100644
--- a/Documentation/core-api/min_heap.rst
+++ b/Documentation/core-api/min_heap.rst
@@ -30,6 +30,26 @@ more expensive. As with the non-inline versions, it is important to use the
macro wrappers for inline functions instead of directly calling the functions
themselves.
+Equality-Aware Heap Maintenance
+-------------------------------
+
+In some workloads, a large number of elements in the heap may be equal under
+the user-defined comparison function. For such cases, the standard
+``min_heap_sift_down()`` implementation, which uses the bottom-up heapify
+strategy, can be inefficient. While bottom-up heapify reduces the number of
+comparisons by approximately 50% for randomly ordered data, it may perform up
+to :math:`2 \times \log_2(n)` comparisons in the presence of many equal
+elements.
+
+To address this, equality-aware versions of heap maintenance APIs are provided.
+These versions use the traditional top-down heapify strategy, which performs
+better - sometimes requiring only :math:`\mathcal{O}(1)` comparisons - when
+many elements are equal.
+
+The equality-aware APIs are suffixed with ``_eqaware``, and serve as drop-in
+replacements for their standard counterparts when equal elements are expected.
+
+
Data Structures
===============
--
2.34.1
