[BUG] RF max_leaves uses FIFO growth instead of best-first growth

[RAMitchell]

Summary

When max_leaves is active, cuML RF consumes the leaf budget in FIFO/breadth-first order. Scikit-learn's equivalent max_leaf_nodes expands the frontier node with the greatest impurity reduction.

This matters for cuml.accel, which maps max_leaf_nodes directly to max_leaves.

Reproducer

The root split below produces two candidate children. Splitting the left child reduces SSE by 100, while splitting the right child reduces it by 1000. With max_leaves=3, only one can be expanded.

import numpy as np
from cuml.ensemble import RandomForestRegressor as CuRF
from sklearn.ensemble import RandomForestRegressor as SkRF
from sklearn.metrics import mean_squared_error

X = np.vstack([
    np.column_stack([np.zeros(100), np.r_[np.zeros(50), np.ones(50)]]),
    np.column_stack([np.ones(10), np.r_[np.zeros(5), np.ones(5)]]),
]).astype(np.float32)

y = np.r_[
    np.ones(50), -np.ones(50),
    np.full(5, 10.0), np.full(5, 30.0),
].astype(np.float32)

models = {
    "cuML": CuRF(
        n_estimators=1, max_depth=16, max_leaves=3,
        max_features=1.0, bootstrap=False, n_bins=16,
        n_streams=1, random_state=0,
    ),
    "sklearn": SkRF(
        n_estimators=1, max_depth=16, max_leaf_nodes=3,
        max_features=1.0, bootstrap=False, random_state=0,
    ),
}

for name, model in models.items():
    model.fit(X, y)
    print(name, mean_squared_error(y, model.predict(X)))

Using cuML 26.08.00 and scikit-learn 1.9.0:

cuML      9.090909
sklearn   0.909091

Both implementations achieve zero MSE without a leaf constraint, so this is not caused by unavailable split thresholds.

Cause

NodeQueue::Pop() takes nodes from the front of a deque, and Push() accepts valid splits in that order until max_leaves is reached. Earlier nodes therefore receive the remaining leaf budget regardless of gain.

Potential fix

When max_leaves is active, use a max-priority queue containing evaluated split candidates:

1. Pop and apply the highest-gain split.
2. Evaluate its children and insert their candidates.
3. Repeat until max_leaves is reached.

An expansion batch size of one reproduces scikit-learn's best-first semantics. The existing batched FIFO builder can remain unchanged when max_leaves == -1.

Merely setting max_batch_size=1 is insufficient unless the FIFO queue is also replaced with a gain-prioritized queue.

I could not find an existing issue covering this specific behavior. #2518 concerns general RF accuracy, while #3764 concerns classification probability aggregation.