p*****3
发帖数: 488 | 1 给一个很大的maxHeap, size n, 数组形式表达，array A
给一个k+constant的数组 Array B，constant<< k << n
求kth max in maxHeap，不能改变maxHeap (Array A只读) |
a********m
发帖数: 15480 | 2 有其它啥要求不？array b做heap扫一下应该是klgk。每次取max然后把它在a里面的直
接children加到heap b里面。 |
p*****3
发帖数: 488 | 3
correct
【在 a********m 的大作中提到】
: 有其它啥要求不？array b做heap扫一下应该是klgk。每次取max然后把它在a里面的直
: 接children加到heap b里面。
|
s*******n
发帖数: 305 | 4
两位大大， 能不能在多说点， 没太明白。
a 为不可写的， 那就没法多次取max?
b 和 a 有重复吗，每次把b中max和a相同的数的孩子放到b中：
1. b中的max不一定是a中的max呀？怎么保证取到a的kth max?
2. 每次把孩子都放到b中， 会不会overflow, 因为b的size只有k+constant, constant
<
操作完后，就是b.size()+1了？
我的确没有理解， 请多讲讲， 谢谢。
【在 a********m 的大作中提到】
: 有其它啥要求不？array b做heap扫一下应该是klgk。每次取max然后把它在a里面的直
: 接children加到heap b里面。
|
a********m
发帖数: 15480 | 5 “求kth max in maxHeap”，所以只考虑a里面的内容，b是空的。
1。a不改变，所以b只需要存a的index就可以了。最开始只有一个值，0，表示a的第一
个元素，最大值。
2。每次把b里面第一个元素取走，添加这个元素在a里面的孩子，最多两个，所以每找
到一个数字b最多增加一个。取k个数字以后b里面元素不可能超过k+1.
constant
【在 s*******n 的大作中提到】
:
: 两位大大， 能不能在多说点， 没太明白。
: a 为不可写的， 那就没法多次取max?
: b 和 a 有重复吗，每次把b中max和a相同的数的孩子放到b中：
: 1. b中的max不一定是a中的max呀？怎么保证取到a的kth max?
: 2. 每次把孩子都放到b中， 会不会overflow, 因为b的size只有k+constant, constant
: <: 操作完后，就是b.size()+1了？
: 我的确没有理解， 请多讲讲， 谢谢。
|
S********t
发帖数: 3431 | 6 这跟一道两sorted数组求kth pair sum异曲同工吧？
【在 p*****3 的大作中提到】
: 给一个很大的maxHeap, size n, 数组形式表达，array A
: 给一个k+constant的数组 Array B，constant<< k << n
: 求kth max in maxHeap，不能改变maxHeap (Array A只读)
|
a********m
发帖数: 15480 | 7 不错，你这么一说是有些像。
【在 S********t 的大作中提到】
: 这跟一道两sorted数组求kth pair sum异曲同工吧？
|
s*******n
发帖数: 305 | 8
多谢秋虫大大， b是空的， 我从最开始就理解错了， 受教了
【在 a********m 的大作中提到】
: “求kth max in maxHeap”，所以只考虑a里面的内容，b是空的。
: 1。a不改变，所以b只需要存a的index就可以了。最开始只有一个值，0，表示a的第一
: 个元素，最大值。
: 2。每次把b里面第一个元素取走，添加这个元素在a里面的孩子，最多两个，所以每找
: 到一个数字b最多增加一个。取k个数字以后b里面元素不可能超过k+1.
:
: constant
|
a********m
发帖数: 15480 | 9 np. 其实最开始俺也没想那么多细节，赫赫。
【在 s*******n 的大作中提到】
:
: 多谢秋虫大大， b是空的， 我从最开始就理解错了， 受教了
|
c********p
发帖数: 1969 | |
h**6
发帖数: 4160 | |
