题目链接
题目描述
从无序序列，找到最小topk个元素。
解题思路
使用大根堆维护最小topk个元素：
- 首先前k个元素建立大根堆（从最后一个非叶节点（数组长度/2-1，结点从0计：大致是最后一个节点j与最后一个非叶节点i满足j=2i+1或j=2i+2，PS数组长度len=j+1，大概是有一些取整的原因设计，总之验证这是对的)至根节点（数组第一个元素）调整）。
- 之后维护这个最小k个元素的大根堆（比较后面的元素与根顶元素，若新元素小则替换掉堆顶元素，并进入调整）。
- 最终堆中元素即为所求。
查找topk时间复杂度：O(nlogk)。
相关知识：堆排序
堆的定义
堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
用数组表示一个堆结构，堆的定义就是：(结点从0计)
大根堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小根堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序步骤
第一步：建堆：从最后一个非叶节点（数组长度/2-1，结点从0计。推导：最后一个节点下标j与最后一个非叶节点i的关系满足j=2i+1或j=2i+2=>i=j/2-1或j/2-0.5,)至根节点（数组第一个元素）调整。
第二步：反复执行交换、调整：将堆顶元素与树最后一个叶节点交换，从上至下调整剩余节点为堆（称为筛选）；再将堆顶元素与最后一个叶节点交换...直到所有元素组成序列。大根堆对应升序，小根堆对应降序。
堆排序特点
- 时间复杂度：平均、最好、最坏均为O(nlogn)
- 相比快排，堆排序的最坏时间复杂度更优，这是堆排序最大的优点。所以堆排序适合记录数n较大的文件，不适合记录数较小的文件。
- 对深度为K的堆，筛选算法关键字比较次数至多为2(K-1)；则在建n个元素，深度为h的堆时，总共进行的关键字比较次数不超过4n（公式见数据结构严蔚敏P282底栏？？）；又，n个结点的完全二叉树深度为log2n」+1,所以最坏时间复杂度O(nlogn).
堆排序参考链接
https://www.cnblogs.com/chengxiao/p/6129630.html
代码
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> maxRootHeap = new ArrayList<Integer>();
if(k<1||k>input.length){
return maxRootHeap;
}
for(int i=0;i<k;++i) {
maxRootHeap.add(input[i]);
}
//建堆
buildMaxRootHeap(maxRootHeap);
//调整
for(int i=k;i<input.length;++i) {
if(input[i]<maxRootHeap.get(0)) {
maxRootHeap.set(0, input[i]);
heapify(maxRootHeap,0,k-1);
}
}
return maxRootHeap;
}
private void buildMaxRootHeap(ArrayList<Integer> maxRootHeap) {
for(int i=maxRootHeap.size()/2-1;i>=0;--i) {
heapify(maxRootHeap,i,maxRootHeap.size()-1);
}
}
//调整以index索引为根节点的堆
private void heapify(ArrayList<Integer> maxRootHeap,int index,int heapSize) {//heapSize 指堆最后一个节点的索引
int lIdx=2*index+1;
int rIdx=2*index+2;
int maxIdx=index;
while(lIdx<=heapSize) {
if(maxRootHeap.get(lIdx)>maxRootHeap.get(index)) {
maxIdx=lIdx;
}
if(rIdx<=heapSize&&maxRootHeap.get(rIdx)>maxRootHeap.get(maxIdx)) {
maxIdx=rIdx;
}
if(maxIdx!=index) {
swap(maxRootHeap,index,maxIdx);
}
else {
break;
}
index=maxIdx;
lIdx=2*index+1;
rIdx=2*index+2;
}
}
private void swap(ArrayList<Integer> heap,int idx1,int idx2) {
int temp=heap.get(idx1);
heap.set(idx1,heap.get(idx2));
heap.set(idx2, temp);
}
}