注意:最小TopK用大顶堆,最大TopK用小顶堆
一、用java 的priorityQueue实现
//最小Top, 用java的PriorityQueue
import java.util.*;
public class Solution{
public ArrayList<Integer<> getLeastNumber_Solution(int[] input, int k){
int n = input.length;
ArrayList<Integer> list = new ArrayList<>();
if(n == 0 || k > n || k == 0) return list;
//大顶堆 降序
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2){
return o2.compareTo(o1);
}
});
//PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, (o1, o2) -> o2 - o1);
for(int i = 0; i < n; i++){
if(maxHeap.size() < k){
maxHeap.offer(input[i]);
}else if(maxHeap.peek() > input[i]){
Integer tmp = maxHeap.poll();
tmp = null;
maxHeap.offer(input[i]);
}
}
for(int i = 0; i < k && !maxHeap.isEmpty(); i++)){
list.add(maxHeap.poll()));
}
return list;
}
}
二、手写堆排序取最小TopK
//手写堆排序取最小topK
public ArrayList<Integer> getLeastNumber_Solution(int[] input, int k){
int n = input.length;
ArrayList<Integer> list = new ArrayList<>();
if(n == 0 || k > n || k == 0) return list;
//1.构建大顶堆
for(int i = k/2 - 1; i >= 0; i--){
//从第一个非叶子结点从下至上,从右至左调整结构
adjustMaxHeapSort(input, i, k - 1);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for(int i = n- 1; i >= 0; i--){
swap(input, 0, i);
adjustMaxHeapSort(input, 0, i);
}
for(int i = 0; i < k; i++){
list.add(input[i]);//将堆顶元素与末尾元素进行交换
System.out.println(input[i]);重新对堆进行调整
}
return list;
}
// 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上)
public void adjustMaxHeapSort(int[] input, int i, int length){
int tmp = input[i];//先取出当前元素i
//从i结点的左子结点开始,也就是2i+1处开始
for(int child = 2*i+1; child <= length; child = child*2+1){
//如果左子结点小于右子结点,k指向右子结点
if(child+1 < length && input[child] < input[child+1] ){
child++;
}
//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
if(input[child] > tmp){
input[i] = input[child];
i = child;
}else{
break;
}
}
input[i] = tmp;//将temp值放到最终的位置
}
public void swap(int[] input, int i, int j){
int tmp = input[i];
input[i] = input[j];
input[j] = tmp;
}
三、快速排序实现
//快排实现
public ArrayList<Integer> getLeastNumber_Solution(int[] input, int k){
int n = input.length;
ArrayList<Integer> list = new ArrayList<>();
if(n == 0 || k > n || k == 0) return list;
int start = 0, end = n - 1;
int index = partition(input, start, end);
while(index != k - 1){
if(index < k - 1){
start = index + 1;
index = partition(input, start, end);
}else{
end = index - 1;
index = partition(input, start, end);
}
}
for(int i = 0; i < k; i++){
list.add(input[i]);
}
return list;
}
public int partition(int[] input, int start, int end){
int pivot = input[start];
while(start < end){
while(start < end && pivot <= input[end]){
end--;
}
input[start] = input[end];
while(start < end && pivot >= input[start]){
start++;
}
input[end] = input[start];
}
input[start] = pivot;
return start;
}