【java】堆排序 最小的k個數

堆排序

二叉堆是一顆完全二叉樹，完全二叉樹可以存放在一維數組中，如果将數組從0開始編号，則對a[i]，它的左子樹及右子樹分别是a[2*i+1]和a[2*i+2]。二叉堆有大根堆和小根堆，是指每個結點的值大于(/小于)它們子結點的值。

調整堆

假設結點a[i]的左子樹和右子樹都已經是最大堆，将根節點為a[i]的樹調整為最大堆。

過程：将a[i]分别與左右子節點比較，然後與其中最大的一個交換位置，交換後的子結點可能違反最大堆的性質，是以要對該子樹遞歸調用堆調整。

建堆

過程：對于完全二叉樹，可知n/2......n-1等結點都是葉子結點，建堆的過程就是對于所有非葉子節點，從後往前地進行堆調整。

堆排序

過程：首先建立堆，之後每次交換最大堆的根(即a[0]，是堆中最大的元素)與最後一個元素的值，堆大小減一，之後堆根的元素不符合最大堆的性質，進行堆調整，直至堆得大小為1，排序完畢。

先輸入n代表數字個個數，之後輸入n個數字，輸出排序後的結果。

樣例輸入：

5

23 32 54 23 12

10

12312 4564 874  23 78 56 456 12 23 85

樣例輸出：

12 23 23 32 54

12 23 23 56 78 85 456 874 4564 12312

import java.util.Scanner;

public class Main {
	public static int[] arr;
	public static int heap_size;
	public static void heap_adjust(int a){
		int left=2*a+1;
		int right=2*a+2;
		if(left>=heap_size||right>=heap_size)
			return;
		int large=a;
		if(arr[left]>arr[large]){
			large=left;
		}
		if(arr[right]>arr[large])
			large=right;
		if(large==a)
			return;
		else{
			int temp=arr[a];
			arr[a]=arr[large];
			arr[large]=temp;
			heap_adjust(large);
		}
	}
	public static void heap_build(){
		for(int i=heap_size/2-1;i>=0;i--){
			heap_adjust(i);
		}
	}
	public static void heap_sort(){
		heap_build();
		while(heap_size>1){
			int temp=arr[0];
			arr[0]=arr[heap_size-1];
			arr[--heap_size]=temp;
			heap_adjust(0);
		}	
	}
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			int n=scanner.nextInt();
			arr=new int[n];
			heap_size=n;
			for(int i=0;i<n;i++){
				arr[i]=scanner.nextInt();
			}
			heap_sort();
			StringBuffer str=new StringBuffer();
			for(int i:arr)
				str.append(i+" ");
			System.out.println(str.substring(0,str.length()-1));
		}
		scanner.close();
	}
}
           

最小的k個數

最小的k個數可以使用快速排序(類似于求第k小的數)的思想完成，這裡介紹使用堆排序思想完成的算法。

先将前K個元素初始化成最大堆，繼續周遊之後的元素，當該元素小于堆根時，将他與堆根元素交換，并調整堆。

類似地，求最大的k個數需要初始化一個大小為k的最小堆。

先輸入n代表數字個個數，k代表要求的元素個數，之後輸入n個數字，輸出最小的k個數。

樣例輸入：

10 4

12312 4564 874  23 78 56 456 12 23 85

樣例輸出：

56 12 23 23

import java.util.Scanner;

public class Main {
	public static int[] arr;
	public static int heap_size;
	public static void heap_adjust(int a){
		int left=2*a+1;
		int right=2*a+2;
		if(left>=heap_size||right>=heap_size)
			return;
		int large=a;
		if(arr[left]>arr[large]){
			large=left;
		}
		if(arr[right]>arr[large])
			large=right;
		if(large==a)
			return;
		else{
			int temp=arr[a];
			arr[a]=arr[large];
			arr[large]=temp;
			heap_adjust(large);
		}
	}
	public static void heap_build(){
		for(int i=heap_size/2-1;i>=0;i--){
			heap_adjust(i);
		}
	}
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			int n=scanner.nextInt();
			int k=scanner.nextInt();
			arr=new int[n];
			heap_size=k;
			for(int i=0;i<n;i++){
				arr[i]=scanner.nextInt();
			}
			heap_build();
			for(int i=heap_size;i<n;i++){
				if(arr[i]<arr[0]){
					arr[0]=arr[i];
					heap_adjust(0);
				}
			}
			StringBuffer str=new StringBuffer();
			for(int i=0;i<heap_size;i++)
				str.append(arr[i]+" ");
			System.out.println(str.substring(0,str.length()-1));
		}
		scanner.close();
	}
}