最近有一个java大神，是蚂蚁支付宝的哦，问了我这么一个问题。我的回答是先将数组分解成两百个小数组或者更多，在开两百个thread进行排序，取最大，然后对这两百个数进行排序，取前三。其实我的思路根本就没有涉及到算法层面，也只是暴力破解。其实这不是最好的做法，因为这样会严重的浪费资源，然后他的回答是堆排序。我的问题是堆排序是怎样实现的，最好用代码体现出来。
PHPz2017-04-18 09:15:57
上位 3 つを並べ替える必要があるのはなぜですか? 3 つの新しい変数スペースを開いて中間結果を保存するだけです。
この方法の計算量は O(nk)、n はデータの総量、k は取得するデータの数です。ヒープソートでもクイックソートでも順序はO(nlogn)です。 k が log(2, 10 ** 8) より小さい場合でも利点はありますが、大きすぎると挿入ソートに堕します。
阿神2017-04-18 09:15:57
N (N>>10000) 個の整数があり、その中で上位 K 個の最大の数値を見つけます。 (Top k アルゴリズム問題と呼ばれます)。 (1) 入力データが大量である、(2) 最初の K のみであるため、入力データ全体を保存して並べ替えることは非常に望ましくありません。この問題は、データ構造の最小ヒープを使用して処理できます。
最小ヒープ。各非リーフ ノードの値は、子ノードの値を超えてはなりません。このようにして、K 個のノードを含む最小ヒープを使用して、K 個の現在の最大値を保存できます (もちろん、ルート ノードはその中の最小値です)。データが入力されるたびに、最初にルート ノードと比較できます。ルート ノードより大きくない場合は破棄し、ルート ノードの値を新しい値に置き換えます。そして最小ヒープを調整します。
K 個のデータのみが保存されるため、最小ヒープの計算量は O(logK) に調整され、TOp K アルゴリズム (問題) の計算量は O(nlogK) となります。
PHP中文网2017-04-18 09:15:57
検索してください
http://www.cnblogs.com/skywang12345/p/3610187.html
証明と導出については、「アルゴリズムの概要」を参照してください
でも、積み上げる必要はありません。結局のところ、探しているのは 3 つの数字だけです...
