堆排序的使用场景——从10万个数里面选出最小的10个

【学习笔记】

前几天手撕了堆排序的基本算法，堆是一种重要的数据结构，不但排序效率相对较快，而且排序时间复杂度也比较稳定。今天就来简单谈谈堆排序其中一种使用场景，还是以“从10万个数里面选出最小的10个”为例，利用堆排序从无序数组里面选择最大（小）的部分元素。

实现原理：用个无序数组模拟10万个数，取无序数组里面前面的10个数字构建一个大顶堆，从第11个数开始逐个与堆顶元素进行比较，小于堆顶元素则入堆，并重新构建大顶堆，这样能保证堆顶元素始终是最大的。循环完毕之后，堆里面的10个元素就是最小的了。

Talk is cheap，show the code~

package sort;

import org.junit.Test;
/**
 * 该算法是堆排序的使用场景
 * @author jsyuger
 * 场景：从10万个数字里面选择最小10个数。
 * 实现：取前面的10个数字构建一个大顶堆，从第11个数开始逐个与堆顶元素进行比较，
 * 		小于堆顶元素则入堆，并重新构建大顶堆，这样能保证堆顶元素始终是最大的。
 * 		循环完毕之后，堆里面的10个元素就是最小的了。
 */
public class MoreHeapSort {
	/**
	 * 堆排序的具体实现
	 * @param arr
	 */
	public void heapSort(int[] arr) {
		for(int i=arr.length - 1 ; i>=2 ; i--) {
			//构建大顶堆
			for(int j = (i-1)/2 ; j>=0 ; j--) { //从第一个非叶子节点开始，与孩子节点作比较
				if(2*j+2<=i && arr[j]<arr[2*j+2]) swapper(arr, j, 2*j+2); //与右孩子比较，2*j+2<=i这个条件主要防止数组越界
				if(arr[j]<arr[2*j+1]) swapper(arr , j , 2*j+1); //与左孩子比较
			}
			//swapper(arr,0,i); //交换根结点和最后一个节点，筛选出最大值
		}
	}
	
	//数组交换两个元素的位置
	private void swapper(int[] arr, int i, int j) {
		int temp = arr[i] ;
		arr[i] = arr[j] ;
		arr[j] = temp ;
	}
	
	@Test
	public void heapSortTest() {
		int array[] = {2 , 5 , 10 , 9 ,12 ,30 ,23 ,48 ,59 ,29 ,4 ,11 ,22 ,54 ,25 ,88 ,90 ,6} ;
		System.out.print("未排序数组：");
		for(int i : array) System.out.print(" " + i);
		System.out.print("\n");
		//取前10个数字构建大顶堆
		int arr[] = new int[10];
		for(int j=0;j<=9;j++)  arr[j] = array[j];
		heapSort(arr); //构建大顶堆
		//从第11个数开始逐个与堆顶元素进行比较，小于堆顶元素则入堆，并重新构建大顶堆
		for(int k=10;k<=array.length - 1 ;k++) {
			if(array[k]<arr[0]) {
				arr[0]=array[k]; //入堆
				heapSort(arr); //构建大顶堆
			}
		}
		System.out.print("最小的10个数：");
		for(int i = 0 ; i<=9 ;i++) System.out.print(" " + arr[i]);
	}
}

控制台输出：

未排序数组： 2 5 10 9 12 30 23 48 59 29 4 11 22 54 25 88 90 6
最小的10个数： 23 22 6 12 10 4 2 11 9 5