g****e
发帖数: 172 | | w****f
发帖数: 684 | 2 min-heap with only 5 element,
or top-k selection? | v****c
发帖数: 29 | 3 一共就5个数，怎么搞都行
by the way, 应该是max heap
【在 w****f 的大作中提到】
: min-heap with only 5 element,
: or top-k selection?
| w****f
发帖数: 684 | 4 Yes, it should be max-heap.
【在 v****c 的大作中提到】
: 一共就5个数，怎么搞都行
: by the way, 应该是max heap
| f*******n
发帖数: 12623 | 5 Find k smallest numbers in a list of size n:
* Use max-heap of size k, iterate through list
O(n log k)
* Turn entire list into min-heap, then pop k times
O(n + k log n)
* Use worst-case linear-time selection algorithm to find the value of the k'
th smallest element, then partition the list with this value, and take the
first k elements
O(n) | h*******e
发帖数: 225 | 6 It is only asking for the five smallest numbers. Forget about min-heap and
linear time selection algorithm. The constant factor is so small that by
just keeping five ints and do comparisons directly you would probably yield
a faster program than all the algorithms you listed here.
k'
【在 f*******n 的大作中提到】
: Find k smallest numbers in a list of size n:
: * Use max-heap of size k, iterate through list
: O(n log k)
: * Turn entire list into min-heap, then pop k times
: O(n + k log n)
: * Use worst-case linear-time selection algorithm to find the value of the k'
: th smallest element, then partition the list with this value, and take the
: first k elements
: O(n)
|
|
