RamakrishnaChilaka commented on code in PR #15140:
URL: https://github.com/apache/lucene/pull/15140#discussion_r2315535741
##########
lucene/core/src/java/org/apache/lucene/util/LongHeap.java:
##########
@@ -216,4 +216,63 @@ public long get(int i) {
long[] getHeapArray() {
return heap;
}
+
+ /**
+ * Restores heap order by moving an element up the heap until it finds its
proper position. Works
+ * with heaps of any arity (number of children per node).
+ *
+ * @param heap the heap array (1-based indexing)
+ * @param i the index of the element to move up
+ * @param arity the number of children each node can have
+ */
+ static void upHeap(long[] heap, int i, int arity) {
+ final long value = heap[i]; // save bottom value
+ while (i > 1) {
+ // parent formula for 1-based indexing
+ final int parent = ((i - 2) / arity) + 1;
+ final long parentVal = heap[parent];
+ if (value >= parentVal) break;
+ heap[i] = parentVal; // shift parent down
+ i = parent;
+ }
+ heap[i] = value; // install saved value
+ }
+
+ /**
+ * Restores heap order by moving an element down the heap until it finds its
proper position.
+ * Works with heaps of any arity (number of children per node).
+ *
+ * @param heap the heap array (1-based indexing)
+ * @param i the index of the element to move down
+ * @param size the current size of the heap
+ * @param arity the number of children each node can have
+ */
+ static void downHeap(long[] heap, int i, int size, int arity) {
+ long value = heap[i]; // save top value
+ for (; ; ) {
+ // first child formula for 1-based indexing
+ int firstChild = arity * (i - 1) + 2;
+ if (firstChild > size) break; // i is a leaf
+
+ int lastChild = Math.min(firstChild + arity - 1, size);
+
+ // find the smallest child in [firstChild, lastChild]
+ int best = firstChild;
+ long bestVal = heap[firstChild];
+
+ for (int c = firstChild + 1; c <= lastChild; c++) {
+ final long v = heap[c];
+ if (v < bestVal) {
+ bestVal = v;
+ best = c;
+ }
+ }
+
+ if (bestVal >= value) break;
+
+ heap[i] = bestVal;
+ i = best;
+ }
+ heap[i] = value; // install saved value
+ }
Review Comment:
I initially put the helpers in LongHeap since the name is more generic, but
I agree that keeping them in `TernaryLongHeap` makes sense for encapsulation
and avoids unused code (for LongHeap) in LongHeap's class. I’ll move them over.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
