最小的k个数
题目：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,
求最大的k个数用最小堆，根节点是堆 的最小值，每次和根节点比较，比根小，舍弃，否则，代替根
求最小的K个数用最大堆，根节点是堆的最大值，每次和根节点比较，比根大，舍弃，否则，代替根。
PriorityQueue 是默认小根堆，根节点是最小值。所以用来求解最大的k个数
public static List<Integer> findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minQueue = new PriorityQueue<>(k); for (int num : nums) { if (minQueue.size() < k || num > minQueue.peek()) minQueue.add(num); if (minQueue.size() > k) minQueue.poll(); }
return new ArrayList<>(minQueue);
}
本题解法：PriorityQueue 是可以指定为大根堆，根节点是最大值。所以用来求解最小的k个数
public static List<Integer> solutionByHeap(int[] input, int k) { List<Integer> list = new ArrayList<>(); if (k > input.length || k == 0) { return list; }
//指定为大根堆。 PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder()); //得到k个最大值 for (int num : input) { if (queue.size() < k) { queue.add(num); } else if (queue.peek() > num){ queue.poll(); //移除头元素，也就是最大值 queue.offer(num); } }
return new ArrayList<>(minQueue);
}
本题解法：手写大根堆，前k个元素是最小的k个元素 为什么从n/2开始建堆呢，因为n/2是最后一个非叶子节点。n/2到n的所有节点都是叶子节点，是最下一层，不需要下沉。比如n=9 树的编号是{[1],[2,3],[4,5,6,7],[8,9]}。n/2=4就是第三层的第一个节点，也是最后一个非叶子节点。
/* 维护 A[0...k-1] 这个大根堆 */ public static List<Integer> topKSmall(int A[], int n, int k) { //初始化前面k个元素 for(int i=k/2; i>=0; --i) AdjustDown(A, i, k); // 先用前面的k个数建大根堆 // 从k开始向后遍历，一直到结束，比如k=3,n可能是很大很大。 for(int i=k; i<n; ++i) { if(A[i] < A[0]) // 如果小于堆顶元素，替换之 { int tmp = A[0]; A[0] = A[i]; A[i] = tmp; AdjustDown(A, 0, k); // 向下调整 } } ArrayList<Integer> result = new ArrayList<Integer>(); for (int i = 0; i < k; i++) { result.add(A[i]); } return result; } /** * * @param arr * @param parentIndex * @param length 指的是堆的有效大小。只在这个范围内下沉 */ public static void AdjustDown(int arr[], int parentIndex, int length) { int temp = arr[parentIndex]; int childIndex = 2 * parentIndex +1; while (childIndex<length) { if (childIndex+1<length && arr[childIndex+1]>arr[childIndex]){ childIndex++; } if(temp>=arr[childIndex]) break; arr[parentIndex]=arr[childIndex]; parentIndex=childIndex; childIndex=2*childIndex+1; } arr[parentIndex]=temp; }
当求最大的k个数字时，只需要把大根堆换成小根堆即可。（下沉的判断条件反一下，入堆的判断条件也反一下）
/* 维护 A[0...k-1] 这个小根堆 */ public static List<Integer> topKBig(int A[], int n, int k) { //初始化前面k个元素 for(int i=k/2; i>=0; --i) AdjustDown(A, i, k); // 先用前面的k个数建小根堆 // 从k开始向后遍历，一直到结束，比如k=3,n可能是很大很大。 for(int i=k; i<n; ++i) { if(A[i] > A[0]) // 如果大于堆顶元素，替换之 { int tmp = A[0]; A[0] = A[i]; A[i] = tmp; AdjustDown(A, 0, k); // 向下调整 } } ArrayList<Integer> result = new ArrayList<Integer>(); for (int i = 0; i < k; i++) { result.add(A[i]); } return result; } /** * * @param arr * @param parentIndex * @param length 指的是堆的有效大小。只在这个范围内下沉 */ public static void AdjustDown(int arr[], int parentIndex, int length) { int temp = arr[parentIndex]; int childIndex = 2 * parentIndex +1; while (childIndex<length) { if (childIndex+1<length && arr[childIndex+1]<arr[childIndex]){ childIndex++; } if(temp<=arr[childIndex]) break; arr[parentIndex]=arr[childIndex]; parentIndex=childIndex; childIndex=2*childIndex+1; } arr[parentIndex]=temp; }
总结:大根堆的解法和堆排序几乎一样，只有两个地方不同，1：大根堆解法只需要对前k个元素建堆，堆排序要对所有元素建堆。2.大根堆解法每次替换堆定元素，堆排序每次是删除堆定元素，把它移到未排序部分 的最后一位
//堆排序 public static void heapSort(int[] arr){ for(int i = arr.length/2;i>=0;i--){ downAdjust(arr,i,arr.length); } System.out.println(Arrays.toString(arr)); //删除堆顶的元素，就是把数组的第一位和最后一位换位置 for (int i = arr.length-1;i>0;i--) { int temp = arr[i]; arr[i]=arr[0]; arr[0]=temp; downAdjust(arr,0,i); //然后把第一个元素下沉，在0到length的区间内 System.out.println(Arrays.toString(arr)); } } public static void downAdjust(int[] arr,int parentIndex,int length) { int temp = arr[parentIndex]; int childIndex = 2 * parentIndex +1; while (childIndex<length) { if (childIndex+1<length && arr[childIndex+1]>arr[childIndex]){ childIndex++; } if(temp>=arr[childIndex]) break; arr[parentIndex]=arr[childIndex]; parentIndex=childIndex; childIndex=2*childIndex+1; } arr[parentIndex]=temp; }