3 ms·
I'm not sure I'm able to visualize this correctly. Let's say we have an array of strings containing the top 20 movies from Rotten Tomatoes: The Wizard of Oz
by biot 11y ago
I'm not sure I'm able to visualize this correctly. Let's say we have an array of strings containing the top 20 movies from Rotten Tomatoes:
The Wizard of Oz
The Third Man
Citizen Kane
All About Eve
Das Cabinet des Dr. Caligari. (The Cabinet of Dr. Caligari)
Modern Times
A Hard Day's Night
The Godfather
E.T. The Extra-Terrestrial
Metropolis
It Happened One Night
Singin' in the Rain
Laura
The Adventures of Robin Hood
Inside Out
Repulsion
Boyhood
North by Northwest
King Kong
Snow White and the Seven Dwarfs
What would this data structure look like?
- mmozeiko 11y agoIt will look like regular plain array of 20 elements (with pointers to your strings). In these 20 elements first one will be the smallest one (use strcmp or similar). Next 4 elements will contain next 4 smallest strings, next 9 next 9 smallest, and then 6 last ones. 1 + 4 + 9 + 6 = 20. In each of sub-heaps (1, 4, 9, 6) elements will be organized in max-heap. Meaning for each element i, x[i] > x[2* i+1] && x[i] > x[2 * i+2].
- bpicolo 11y agoFrom my understanding it would be roughly: https://gist.github.com/bpicolo/32a7fc775ce1810c88a0 https://gist.github.com/bpicolo/32a7fc775ce1810c88a0
- mmozeiko 11y agoI won't be array of arrays. It will be just one array.
- bpicolo 11y agowe decompose an array of size 35 into: an array of size 1 followed by arrays of sizes 4, 9, 16, 5 Then again, maybe he means `mentally decompose` in terms of pretending they're separate arrays? I interpreted it as `visualize this data structure`.
- sethammons 11y agoThat is the way I took it too
- dubroff 11y agoI also originally thought he had an array of arrays, but now I I think the run-times he mentioned for insertion and deletion would only work for a single array, not an array of arrays.