先駆者様

結論

解説

と言っても、アルゴリズムは先駆者様とほぼ同じ。
そのため、差分を説明する。

複雑スコアの計算：先駆者様

const error = (hist.reduce((prev, cur, i) => prev + cur * (i - avg) ** 2, 0) / num) ** 0.5;

先駆者様は最後に0.5乗しているが、ただ単に大小を比較するだけならする必要がないため私はしなかった。
とはいえ、後々係数をかけたりして弄りまわすので好みの問題。

複雑スコアの計算：自分

let roughnessSum = 0;
for (const {r, g, b} of colorList) {
    // マンハッタンとユークリッド どっちがよいのだろうか
    // roughnessSum += Math.abs(block.r - r) + Math.abs(block.g - g) + Math.abs(block.b - b);
    roughnessSum += (block.r - r) ** 2 + (block.g - g) ** 2 + (block.b - b) ** 2;
}
if (block.width < 2 || block.height < 2) {
    block.roughness = Number.NEGATIVE_INFINITY;
}
else {
    block.roughness = (roughnessSum / colorList.length) * (pixelCount / originalPixelCount);
}

四分割ができないほど小さい領域はマイナス無限大をセットしている。（今考えると0でもよかった。）

また、先駆者様の「領域のサイズ」「ある領域が分割されすぎる場合があるのでは？」の問題は

block.roughness = (roughnessSum / colorList.length) * (pixelCount / originalPixelCount);
// block.roughness = 分散 * 面積の割合

とすることで回避を試みた。
小さいエリアは面積の割合が0に近づくため選ばれにくくなるという訳だ。

その他、丸で描いてみても面白そうなので実装した。

また私は画像を10000回分割しても大して重くならなかったため、ヒープうんぬんは利用しなかった。
処理が重くなるとしたら、最大スコア探しよりも画像の加工、描画処理のほうが大きな要因だと思うが、どのくらい速くなるのか少し気になる。

以上。

全体のソースはこ↑こ↓

おまけ（Bad Apple But Quadtree）

まさかな…と思ってググったら既存だった。。。

チラ裏

四分割ではなくて、二分割でもよいのでは？
複雑度のスコアが0のもの（単色しかないブロック）が選択されたら分割せずに処理を終了すべきでは？→対応した。