For reasons unknown (for now) bisect kmeans does not pass tests:
Should be:

Iteration 0, inertia 144.0.
Iteration 1, inertia 78.0.
Converged at iteration 1: strict convergence.
New centroids from bisection: [[ 3. 1.] [-6. -2.]]
Iteration 0, inertia 28.0.
Iteration 1, inertia 16.0.
Converged at iteration 1: strict convergence.
New centroids from bisection: [[ 3. -2.] [ 3. 4.]]

expected_centers = [[10, 2], [10, 8], [1, 2]]

Got:

Iteration 0, inertia 96.0.
Iteration 1, inertia 78.0.
Converged at iteration 1: strict convergence.
New centroids from bisection: [[-6. -2.] [ 3. 1.]]
Iteration 0, inertia 28.0.
Iteration 1, inertia 22.0.
Converged at iteration 1: strict convergence.
New centroids from bisection: [[ 3. 3.] [ 3. -3.]]

bisect_means.cluster_centers_ = [[ 1., 2.], [10., 7.], [10., 1.]]

And assertion error as the result. This happens without any weighting of the input at all.

The test was not robust and very sensitive to rng. Since your changes impact the initialization (even without sample weights), this test started to fail.

I pushed a more robust version of the test that is not subject to rng. The clusters will always be the same no matter the initialization (up to a permutation).

LGTM. Thanks @glevv

We could in a subsequent PR add the possibility to pass sample_weight with a callable. We should be careful to be backwards compatible so we might need to look at the signature before trying to pass the weights.

@glevv If you feel like you want to have a look, feel free to propose a PR.