堆排序 与 优先级队列 实现

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 block
			e.printStackTrace();
		}
		*/
		sort.heapSort(a);//测试堆排序
		System.out.println("-------------------------------------------");
		
		for (int i : a) {
			System.out.print(i+",");
		}
	}
}