bfprt算法求TopK

中位数的中位数算法 最坏时间复杂度 $O(n)$

在做topk问题时，最容易想到的就是先对所有数据进行一次排序，然后取其前k个。但问题有二：

快排时间复杂度 $O(nlogn)$ ，但最坏时间复杂度 $O(n^2)$
我们只要前k大的，而对其余的数也进行了排序，浪费了大量排序时间。

除了这种方法堆排序也是一个比较好的选择，可以维护一个大小为k的堆，时间复杂度为 $O(nlogk)$

堆排序topk

Heap是一种数据结构具有以下的特点：
1）完全二叉树；
2）heap中存储的值是偏序；
Min-heap: 父节点的值小于或等于子节点的值；
Max-heap: 父节点的值大于或等于子节点的值；
一般都用数组来表示堆，i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2 i + 1和2 i + 2
堆中每次都删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。

# 大根堆比较器 top小
public  static class MaxheapComparator implements Comparator<Integer>{
  @Override
  public int compare(Integer o1, Integer o2){
    return o2-o1;
  }
}
public static PriorityQueue getMinKNumsByHeap(int[] arr,int k){
  if(k<1 || k>arr.length){
    return null;
  }
  PriorityQueue<Integer> kHeap = new PriorityQueue<Integer>(k, new MaxheapComparator());
  for(int i=0;i!=k;i++){
    kHeap.add(arr[i]);
  }
  for(int i=k;i!=arr.length;i++){
    if(arr[i]<kHeap.peek()){ // 返回第一个元素，而不从此PriorityQueue中删除一个元素。
      kHeap.poll(); // 返回第一个元素，并从此PriorityQueue中删除一个元素。
      kHeap.add(arr[i]);
    }
  }
  return kHeap;
}
public static void main(String[] args) {
         int[] arr = { 1, 3, 2, 5, 9 };
         // 测试普通方法
         System.out.println(getMinKNumsByHeap(arr, 1).peek());
         System.out.println(getMinKNumsByHeap(arr, 2).peek());
         System.out.println(getMinKNumsByHeap(arr, 3).peek());
         System.out.println(getMinKNumsByHeap(arr, 4).peek());
         System.out.println(getMinKNumsByHeap(arr, 5).peek());
     }

原理过程

在快排基础上，先通过判断主元位置与k的大小使递归的规模变小。

再通过修改快速排序中主元的选取方法来降低快速排序在最坏情况下的时间复杂度。

选取主元
以选取的主元为分界点，把小于主元的放到左边，大于主元的放到右边
分别对左边和右边进行递归，重复上述过程

数组被划分为了 N/5 个小部分，每个部分的5个数排序需要 O(1) ，所有部分排完需要 O(N/5)=O(N)
取出每个小部分的中位数，一共有 N/5 个，递归调用BFPRT算法得到这些数中第 (N/5)/2 小的数（即这些数的中位数），记为 pivot
以 pivot 作为比较，将整个数组划分为 pivot 三个区域
判断第K小的数在哪个区域，如果在 = 区域则直接返回 pivot ，如果在 < 或 > 区域，则将这个区域的数递归调用BFPRT算法
base case ：在某次递归调用BFPRT算法时发现这个区域只有一个数，那么这个数就是我们要找的数

public static int getMinKthNum(int[] arr, int k){
  if(arr==null || k>arr.length){
    return Integer.MIN_VALUE;
  }
  int[] copyArr = Arrays.copyOf(arr, arr.length);
  return BFPRT(copyArr, 0, arr.length-1, k-1);
}
// 取出每个小部分的中位数，一共有 N/5 个，递归调用BFPRT算法得到这些数中第 (N/5)/2 小的数（即这些数 的中位数），记为 pivot. 以 pivot 作为比较，将整个数组划分为 <pivot , =pivot , >pivot 三个区域
private static int BFPRT(int[] arr, int begin, int end, int i){
  if(begin==end) return arr[begin];
  int pivot = medianOfMedians(arr, begin, end);
  int[] pivotRange = partition(arr, begin, end, pivot);
  if(i>= pivotRange[0] && i<=pivotRange[1]){
    return arr[i];
  } else if(i<pivotRange[0]){
    return BFPRT(arr, begin, pivotRange[0]-1, i);
  } else{
    return BFPRT(arr, pivotRange[1]+1, end, i);
  }
}

private static int[] partition(int[] arr, int begin, int end, int pivot){
  int L= begin-1;
  int R= end + 1;
  int cur = begin;
  while(cur!=R){
    if(arr[cur]>pivot){
      swap(arr, cur, --R);
    } else if(arr[cur]<pivot){
      swap(arr, cur++, ++L)
    } else{
      cur++;
    }
  }
  return new int[]{L+1, R-1};
}

private static int medianOfMedians(int[] arr, int begin, int end){
  int num = end - begin +1;
  int offset = num % 5 ==0 ? 0 : 1;
  int[] medians = new int[num/5 + offset];
  for(int i=0;i<medians.length; i++){
    int beginI = begin+i*5;
    int endI = beginI + 4;
    medians[i] = getMedian(arr, beginI, Math.min(endI, end));
  }
  return BFPRT(medians, 0, medians.length-1, medians.length/2);
}

private static int get Median(int[] arr, int begin, int end){
  insertionSort(arr, begin, end);
  int sum = end+begin;
  int mid = (sum/2) + (sum%2);
  return arr[mid];
}
private static void insertionSort(int[] arr, int begin, int end){
  if (begin>=end) return;
  for(int i=begin+1; i<=end; i++){
    for(int j=i; j>begin; j--){
      if(arr[j] < arr[j-1]){
        swap(arr, j, j-1);
      }else{
        break;
      }
    }
  }
}

时间复杂度

最坏情况下是 $O(n)$

令 $T(n)$ 为所求的时间复杂度，则：

$\begin{equation}\begin{split} T(n) \le T(\frac {n}{5}) + T(\frac{7n}{10}) + c\cdot n \end{split}\end{equation}$

$T(\frac n 5)$ 来自 GetPivotIndex()，n 个元素，5 个一组，共有 $⌊\frac n5⌋$ 个中位数；
$T(\frac {7n}{10})$ 来自 BFPRT()，在 $⌊\frac n5⌋$ 个中位数中，主元 x 大于其中 $\frac 12⋅\frac n5=\frac n{10}$ 的中位数，而每个中位数在其本来的 5 个数的小组中又大于或等于其中的 3 个数，所以主元 x 至少大于所有数中的 $\frac n{10}⋅3=\frac {3n}{10}$ 个。即划分之后，任意一边的长度至少为 $\frac 3{10}$，在最坏情况下，每次选择都选到了 $\frac 7{10}$ 的那一部分。
$c⋅n$ 来自其它操作，比如 InsertSort()，以及 GetPivotIndex() 和 Partition() 里所需的一些额外操作。

设 $T(n)=t⋅n$，其中 t 为未知，它可以是一个正常数，也可以是一个关于 n 的函数，代入上式：

$\begin{align} t⋅n&≤\frac {t⋅n}5+\frac{7t⋅n}{10}+c⋅n \tag{两边消去 n}\\ t&≤\frac t 5+\frac {7t}{10}+c \tag{再化简}\\ t&≤10c \tag{c 为一个正常数} \end{align}$

其中 c 为一个正常数，故t也是一个正常数，即 $T(n)≤10c⋅n$，因此 $T(n)=O(n)$，至此证明结束。

接下来我们再来探讨下 BFPRT 算法为何选 5 作为分组主元，而不是 2, 3, 7, 9 呢？

首先排除偶数，对于偶数我们很难取舍其中位数，而奇数很容易。再者对于 3 而言，会有 $T(n)≤T(\frac n 3)+T(\frac {2n}3)+c⋅n$，它本身还是操作了 n 个元素，与以 5 为主元的 $\frac {9n}{10}$ 相比，其复杂度并没有减少。对于 7，9，… 而言，上式中的 10c，其整体都会增加，所以与 5 相比，5 更适合。