堆的更新/top K问题

在面老虎集团的时候被问到：已知昨天100万股票的前10名，今天股票更新了，我想知道今天的前10名，当时一脸懵逼。甚至不知道他想让我用堆来处理！

算法描述：

我们首先取10万个元素中的前10个元素来建立由10个元素组成的最小堆。这样堆顶元素便是当前已知元素的第10大的数；然后依次读取剩下的99990个元素，若读取的元素比堆顶元素大，则将堆顶元素和当前元素替换，并自堆顶向下调整堆；这样读取完所有元素后，堆中的10个元素即为这10万个数最大的10个数，同时堆顶元素为这10万个元素第10大元素。再对这10个元素排序就是前10名。
时间复杂度：
设从N个数中找M个最大数
每次重新恢复堆的时间复杂都为O(logM),最多供进行了（N-M）次恢复堆操作，顾时间复杂度为O(NlogM)。

从第i个点向下调整堆的过程

//  从i节点开始向下调整,n为节点总数，从i开始计算 i节点的子节点为 2*i+1, 2*i+2
public static void MinHeapDown(int a[], int i, int n)
{
    int j, temp;
    temp = a[i];
    j = 2 * i + 1;
    while (j < n)
    {
        if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的
            j++;

        if (a[j] >= temp)//最小的都大于父节点，说明父节点最小了
            break;

        a[i] = a[j];     //把较小的子结点往上移动,替换它的父结点
        i = j;
        j = 2 * i + 1;
    }
    a[i] = temp;
}

建立最小堆的过程

从最后一个非叶节点开始，依次进行向下调整操作，保证当前节点的所有子节点是满足最小堆的，然后一直到根节点，保证这个堆是满足小顶堆的

//建立最小堆
public static void MakeMinHeap(int a[], int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        MinHeapDown(a, i, n);
}

替换堆顶元素

当来一个新数，需要替换堆顶元素时，替换堆顶元素，然后，从堆顶元素向下进行一次调整，即可使新堆重新满足小顶堆

//如果当前值key>堆顶元素，则才进行替换操作，然后进行向下调整
public static void MinHeapReplaceHeader(int a[], int n,int key)
{
        a[0] = key;
        MinHeapDown(a, 0, n);
}

重新排列这10个数据

public static void MinHeapDeleteNumber(int a[], int n)
{  
for(int i=n-1;i>=0;i--){
    //每次输出一个最小值后的调整过程
    int temp = a[0];
    a[0] = a[i];
    a[i] = temp;
    MinHeapDown(a, 0, i);
}
    //进行遍历，输出最终k个值的过程
     System.out.println(Arrays.toString(Arrays.copyOfRange(a,0,10)));
}

主函数

public static void main(String[] args) {
    int arr[] = {7, 3, 845, 545, 145, 2,10,48,65,2,0,51,5,8,2,6,4,2,4,5,1,7,554,156,156,15,123,132,0,23,31,56};
    MakeMinHeap(arr,10);
    for(int i=10;i<arr.length;i++){
        if(arr[i]>arr[0])
        MinHeapReplaceHeader(arr,10,arr[i]);
    }
    MinHeapDeleteNumber(arr,10);
    //[845, 554, 545, 156, 156, 145, 132, 123, 65, 56]
}