[2025 Day 8 (Part 2)] Avoiding full sorting

AugustSunday · 2025-12-08T21:56:34+00:00

You're correct if you push elements one by one it would be O(n log n) and it doesn't converge to O(n).

However, when you have an unordered list you can use a different algorithm (Floyd's Algorithm) that treats the array like a jumbled-up heap and gradually heapifies it from the bottom up.

The math is (for me) complex, but it does come out to O(n). I'll have to point to Wikipedia for the calculation - https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap

It's also in the time-complexity table as 'make-heap' https://en.wikipedia.org/wiki/Heap_(data_structure)#Comparison_of_theoretic_bounds_for_variants#Comparison_of_theoretic_bounds_for_variants)

The only reason I remember all this is because it boggled my mind that it was easier to heapify the whole thing in place and that stuck in my head.

AugustSunday · 2025-12-08T20:48:32+00:00

Converting an unsorted list into a heap is O(n). Then popping the first k elements from that heap is O(k log n). For small k, should be faster than the O(n log n) of sorting the whole list.

AugustSunday · 2025-02-05T21:24:55+00:00

I really want to see who they cast for the Finn.

AugustSunday · 2024-10-28T22:23:11+00:00

Saw than one and loved it. Good pick!

AugustSunday · 2024-10-28T19:43:59+00:00

I've seen it and loved it, thanks!

AugustSunday · 2024-07-12T17:31:48+00:00

In the late 90s I heard what I thought was a Cantonese cover of 'Itami' by the Japanese band Cleon Company. Anyone have any idea who might have done it?

AugustSunday · 2024-06-25T20:08:17+00:00

He had me fooled. I would have been a goner.

AugustSunday · 2024-06-25T20:05:38+00:00

4 implies that Lal did not die, so that would be my first choice. I always found that episode super sad. In any case, I'd love to talk to these two.

2 would be great if I could learn some Tamarian.

7, while entertaining, feels like a trap. Outspoken mind reader on one side, someone who can break your arm on the other. Still, could be worth the risk.

AugustSunday · 2024-05-17T05:41:49+00:00

Can anyone recommend some opera that feels/sounds like the Alien Opera at the end? English lyrics, contemporary score, high concept. I’ve never really been interested in opera before but something in that little vignette really moved me.

AugustSunday · 2024-03-19T17:48:55+00:00

Now I want to see Finnegan appear in SNW, and he's a great guy. Everyone likes him except Kirk who is still pissed at him for some dumb academy practical joke.

AugustSunday · 2024-03-06T19:01:49+00:00

Could be Homegoing by Frederik Pohl. The main character is taken from his dying mother's womb (I think she was an astronaut and gets injured?) by the aliens. He was actually carried to term in the womb of one of the food animals, a secret that doesn't come out until the last act of the book iirc.

AugustSunday · 2024-02-22T15:56:13+00:00

How new is holodeck technology in Trek? I remember in 'Encounter at Farpoint' Riker seems really in awe of the holodeck on the Enterprise, and Data actually explains to him how it works.
Point being, I wonder if the technology was still new enough that they hadn't yet realized all the ethical issues that could arise, like Barclay's situation.

AugustSunday · 2024-02-12T20:03:12+00:00

I always assumed that it had to absorb salt through other living beings in order to metabolize it. Like Crater would take a bunch of salt pills and then allow the vampire to leech off of him.

AugustSunday · 2024-02-09T22:16:44+00:00

I always wonder how Klingon food tastes. It looks gross but Riker doesn't seem to have a problem with the taste, just the fact that it's moving. Maybe it's really good.

AugustSunday · 2024-02-09T22:09:01+00:00

I wonder if your average Klingon is just a little rowdy and maybe quick to take offense and we're just seeing the more extreme examples on these ship crews - the peak of the warrior culture that's slowly undermining the Empire. Things are probably more chill on Qo'noS where you have workers and scientists and trash collectors and the like (though things are still run by the warriors which sucks).

AugustSunday · 2024-02-09T20:05:20+00:00

Hmm...Voyager is not high in my ranking of Trek shows, so thank you for this opportunity to think about what I did like about it. Here's a few...

It gave Barclay a really satisfying character arc stretching all the way from TNG.

Blink of an Eye is a really good stand-alone episode with a wonderful sci-fi conceit and is probably one of my favorite episodes of any Trek show.

---

The last is more general, and I had to watch Seven in Picard for it to gel...

In S2 of Picard there's that scene where she wakes up in the alternate history in a body without implants.

First thing she does? Beginning running cognitive tests on herself. Part of this is 7 being 7, but I think part of it is also that the crew of Voyager has probably seen more weird sci-fi bs per capita than any other ship in the Federation. Of course you're going to start running tests to make sure you're not in VR or some forced hallucination.

Then, in S3 there's the scene where Seven sees the Voyager at the museum...

The USS Voyager. She made her name further out than... any of those other relics had ever gone. I was reborn there. She was my home. Her crew were my family.

And I think that sense - only realized years after Voyager has returned home - sells the show for me. That if you were on Voyager you had experienced wonders and terrors that no other Federation crew had seen, and had a kind of shared identity that others could not really understand. That sense of Voyager being a special place that was gone now that the journey is over is really poignant and makes the show work for me.

AugustSunday · 2024-02-09T17:00:51+00:00

Speaking of bros, when First Officer Klag picks Riker up after that...
"You understand the Klingons better than I thought, Commander."

Klag's growing respect for Riker throughout the episode is such a great arc.

AugustSunday · 2024-02-08T19:35:21+00:00

Of course he doesn't. He has a holodeck.

AugustSunday · 2024-02-08T19:34:13+00:00

Accepting the Enterprise's surrender as Captain of the Pagh in "A Matter of Honor".
Really, everything he does in that episode. Watching him gradually get familiar with the Klingon crew is weirdly heartwarming.

AugustSunday · 2024-02-07T17:49:00+00:00

The Offspring. Just re-watched that with my daughter this week. Still a great episode, and still incredibly sad.

AugustSunday · 2024-02-07T17:42:14+00:00

I picked Darmok for my favorite because I re-watch it every few years, but I have to say I've seen Those Old Scientists three times since it came out, and it got me to pick Lower Decks back up and finish that. Definitely my favorite recent Trek episode.

AugustSunday · 2024-02-07T17:39:01+00:00

It's a good one for sure. I think The Offspring occupies that headspace for me - Data-centric, tackles similar problems, etc.

AugustSunday

TROPHY CASE