src/nsmallest.js

import {min} from '@iterable-iterator/reduce';
import {sorted} from '@iterable-iterator/sorted';
import {forwardRangeIterator} from '@iterable-iterator/range';
import {iter} from '@iterable-iterator/iter';
import {_zip2} from '@iterable-iterator/zip';
import {reversed} from '@total-order/reversed';
 
import {keeporder} from './core/index.js';
 
import heapify from './heapify.js';
import heapreplace from './heapreplace.js';
 
export default function nsmallest(compare, n, iterable) {
	if (n === 1) {
		const sentinel = {};
 
		const result = min(compare, iterable, sentinel);
 
		return result === sentinel ? [] : [result];
	}
 
	if (iterable.length !== undefined && n >= iterable.length)
		return sorted(compare, iterable);
 
	const it = iter(iterable);
 
	const result = Array.from(
		_zip2(forwardRangeIterator(0, n, 1), it),
		([i, elem]) => [elem, i],
	);
 
	if (result.length === 0) return result;
 
	const h = heapify(keeporder(reversed(compare)), result);
 
	let top = result[0][0];
 
	let order = n;
 
	for (const elem of it) {
		if (compare(elem, top) < 0) {
			heapreplace(h, [elem, order]);
 
			top = result[0][0];
 
			++order;
		}
	}
 
	return sorted(
		compare,
		Array.from(result, (r) => r[0]),
	);
}