[General Doubt]: Why tiny-queue shift is faster than native array shift?

[gdad-s-river]

Non CS, recent graduate, so no CS 101 to rescue. I understood the code, but why tiny-queue shift method is faster than array shift?

Thanks!

[nolanlawson]

I answered on Mastodon, but I'll paste it here:

In principle, because tiny-queue is just a linked list, a shift() is O(1), whereas on an array list a shift() would require copying all items one position over, so it's potentially O(n). (Unless the implementation is clever enough to just keep a pointer to the first item and move it over.)

That said, this needs benchmarking to prove the point. JS engines have lots of clever optimizations under the hood, so tiny-queue is not guaranteed to be faster (and it's certainly not faster in all cases, e.g. for large lists where you never call shift()).