最近有一个java大神，是蚂蚁支付宝的哦，问了我这么一个问题。我的回答是先将数组分解成两百个小数组或者更多，在开两百个thread进行排序，取最大，然后对这两百个数进行排序，取前三。其实我的思路根本就没有涉及到算法层面，也只是暴力破解。其实这不是最好的做法，因为这样会严重的浪费资源，然后他的回答是堆排序。我的问题是堆排序是怎样实现的，最好用代码体现出来。
PHPz2017-04-18 09:15:57
왜 상위 3개를 정렬해야 하나요? 중간 결과를 저장하려면 세 개의 새로운 변수 공간을 열어보세요.
이 방법의 복잡도는 O(nk)이며, n은 전체 데이터 양, k는 얻어야 하는 데이터 개수입니다. 힙 정렬이든 퀵 정렬이든 순서는 O(nlogn)입니다. k가 log(2, 10 ** 8)보다 작을 때 여전히 이점이 있습니다. 너무 크면 삽입 정렬로 변질됩니다.
阿神2017-04-18 09:15:57
N(N>>10000)개의 정수가 있습니다. 그 중에서 가장 큰 K개 숫자를 찾으세요. (상위 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개만 찾으면 되는데...
