5,185 karma · joined July 27, 2009
That way, roughly half the nodes are leaves (requiring no work), a quarter are at the second-to-last level (requiring at most 1 comparison/swap), an eighth at the third-to-last level (requiring at most 2 comparisons/swaps), and so on. Summing up 1 n/4 + 2 n/8 + ... gets you O(n) total complexity.
See https://en.wikipedia.org/wiki/Heapsort?useskin=monobook#Vari...
Debian is great but I can't say this is a shared experience. In particular, I've been bitten by Debian's heavy patching of kernel in Debian stable (specifically, backport regressions in the fast-moving DRM subsystem leading to hard-to-debug crashes), despite Debian releases technically having the "same" kernel for a duration of a release. In contrast, Ubuntu just uses newer kernels and -hwe avoids a lot of patch friction. So I still use Debian VMs but Ubuntu on bare metal. I haven't tried kernel from debian-backports repos though.
Go's implementation of JSON format for protobufs also does this: https://protobuf.dev/reference/go/faq/#unstable-json
> To avoid giving the illusion that the output is stable, we deliberately introduce minor differences so that byte-for-byte comparisons are likely to fail.
>The organ is, together with the clock, the most complex of all mechanical instruments developed before the Industrial Revolution. Among musical instruments its history is the most involved and wide-ranging, and its extant repertory the oldest and largest. Despite its essentially indirect and therefore relatively inflexible production of sound, no other instrument has inspired such avowed respect as the organ, ‘that great triumph of human skill … the most perfect musical instrument’ (Grove), ‘in my eyes and ears … the king of instruments’ (Mozart, letter to his father, 17–18 October 1777).
Stephen Malinowski's famous YouTube channel of animated graphical scores has a great selection of organ pieces: https://www.youtube.com/watch?v=JXaCmhAMnHs&list=PLA20FE13E9...
St. Cecilia, pray for us!
I also encourage everyone to read CFTC response to the Vatican's (!) Congregation for the Doctrine of the Faith https://www.cftc.gov/PressRoom/SpeechesTestimony/giancarlore... It talks about about the social utility of derivatives and refutes the narrative that they are basically tools of "speculation." Traders take on risks others can't bear, creating massive economic value that ripples through the entire system.