Timeline for Find k max integers of an array -- Min Heap vs. Selection Algo vs. Selection Sort
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 15 at 20:37 | comment | added | gnasher729 | K = 100,000: If your minheap contains the 100,000 largest item so far, and you examine item m, its position in the array is anywhere from 1 to m. The largest 100,000 items belong into the min_heap, the probability that item #m belongs there is k / m. The number of insertions into the minheap is about the integral of k/m for m from k to n, that’s k * log (n/k) insertions. The code is absolutely correct, but at some point if k is large enough it doesn’t run in O(n) anymore. | |
| Jul 14 at 20:01 | comment | added | J_H | @gnasher729, I invite you to play around with it. I agree that size (1e7, 1e3) is no problem. // For any random distribution (Gaussian, exponential, uniform, ...), it's always the same problem as long as we have distinct values. So it's enough to talk about the rank number of each observation, which the code above does. And then if a few values turn out to be non-unique, no big deal. If there's many collisions (e.g. boolean or enum values) then we're better off with counters and computing a histogram). | |
| Jul 14 at 19:58 | history | edited | J_H | CC BY-SA 4.0 |
Add log-log plot.
|
| Jul 14 at 18:56 | history | edited | J_H | CC BY-SA 4.0 |
add picture
|
| Jul 14 at 13:51 | comment | added | gnasher729 | Just make sure k is not too large. Since the values in the minheap are initially not very large, I think you will have k log (n/k) insertions into the heap, taking O(log k) time, for a total of O(k log k log (n/k)) operations, and you want k small enough so this remains O(n). With n = 10,000,000 and k = 1,000 it’s no problem. | |
| Jul 13 at 3:12 | history | edited | J_H | CC BY-SA 4.0 |
added 1 character in body
|
| Jul 13 at 2:45 | history | edited | J_H | CC BY-SA 4.0 |
added 196 characters in body
|
| Jul 13 at 2:36 | history | edited | J_H | CC BY-SA 4.0 |
added 290 characters in body
|
| Jul 13 at 2:27 | history | answered | J_H | CC BY-SA 4.0 |