Comment by biot | Hacker News Reader

Comment by biot | Hacker News Reader

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?

It 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].

From my understanding it would be roughly: https://gist.github.com/bpicolo/32a7fc775ce1810c88a0

I won't be array of arrays. It will be just one array.

  we 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`.

That is the way I took it too

I 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.

Reply on news.ycombinator.com