海量資料擷取TopK、堆排序，快速排序實作

注意：最小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;
}