堆排序 与 优先级队列 实现
import java.util.Random;public class Sorts {private int heapsize = 0;Sorts(int[] a){heapsize = a.length-1;}int parent(int i){return (i+1)/2-1;}int left(int i){return 2*(i+1)-1;}int right(int i){return 2*(i+1);}//最大堆void max_heap(int[] a, int i){int l =left(i)-1;int r = right(i)-1;int largest = i;if (l<=heapsize&&a[i]<a[l]) {largest = l;}else {largest = i;}if (r<=heapsize&&a[r]>a[largest]) {largest = r;}if (largest!=i) {a[i]=a[i]+a[largest];a[largest]=a[i]-a[largest];a[i]=a[i]-a[largest];max_heap(a, largest);}}//建大根堆void build_heap(int[] a){for (int i = heapsize/2-1; i>=0; i--) {max_heap(a, i);}}//堆排序void heapSort(int[] a){build_heap(a);for (int i = heapsize; i>0; i--) {a[0]=a[0]+a[i];a[i]=a[0]-a[i];a[0]=a[0]-a[i];heapsize--;max_heap(a, 0);}}//优先级队列提取最大值int heapExtractMax(int[] a)throws Exception{build_heap(a);if (heapsize<0) {throw new Exception("heap underflow");}int max = a[0];a[0]=a[heapsize];heapsize--;max_heap(a, 0);return max;}//提高关键字优先级void heapIncreaseKey(int[] a, int i, int key)throws Exception{if (key<a[i]) {throw new Exception("new key is smaller then current key");}a[i] = key;while (i>0&&a[parent(i)]<a[i]) {a[i]= a[i]+a[parent(i)];a[parent(i)]=a[i]-a[parent(i)];a[i]=a[i]-a[parent(i)];i=parent(i);}}//插入关键字void maxHeapInsert(int[] a, int key)throws Exception{heapsize++;a[heapsize]=Integer.MIN_VALUE;heapIncreaseKey(a, heapsize, key);}public static void main(String[] args) {int[] a = new int[10];Random random = new Random(47);for (int i = 0; i < a.length; i++) {a[i]=random.nextInt();}for (int i : a) {System.out.print(i+",");}System.out.println("-------------------------------------------");Sorts sort = new Sorts(a);//测优先级队列 （和 堆排序 要分开来使用）/*try {System.out.println(sort.heapExtractMax(a));} catch (Exception e) {// TODO Auto-generated catch blocke.printStackTrace();}*/sort.heapSort(a);//测试堆排序System.out.println("-------------------------------------------");for (int i : a) {System.out.print(i+",");}}}?