二叉堆是一颗完全二叉树，完全二叉树可以存放在一维数组中，如果将数组从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的最小堆。
先输入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(); } }
