/** *实现最大堆 *用数组存储 *小优化：将swap用赋值代替，先不急着交换，先复制，再移动，最后赋值 *第一种堆排序，从小到大排序 *时间复杂度为O(nlogn) *空间复杂度O（n） */
public class MaxHeap { private int count; //记录堆中存储元素的个数 private static int[] data; //用数组存储二叉堆 private int capacity; public MaxHeap(int capacity) { //在构造方法中初始化 count=0; data=new int[capacity+1];//因为根节点从1开始，所以存储空间加1 //不能省略，否则默认类中的capacity为0； this.capacity=capacity; } //判断堆是否为空 boolean isEmpty() { return count==0; } //输出堆中元素个数 int size() { return count; } public int getCapacity() { return this.capacity; } //向堆中添加元素 public void insert(int item ) { //先将添加的元素加到最后一个元素后面 //有索引还得考虑索引越界问题，最好的解决方案是动态扩展堆 //这样可以不受堆容量限制，容量不足开辟新空间 if(count++<=getCapacity()) { //count指向所添加的元素 data[count]=item; //再将item向上移动，与父节点比较，如果比父节点大，则交换 shiftUp(count); } } //向上移动，将item与父节点比较，如果比父节点大，则交换 private void shiftUp(int i) { while(i>1&&data[i]>data[i/2]) { swap(i,i/2); i/=2; } } //从堆中取出元素，优先队列思想 public int extractMax() { if(count<=0) return 0; //先取出最大的（优先级高的） int max=data[1]; //将堆中最后一个元素存入第一元素的位置 swap(1, count); count--; //将第一个元素向下移，找到合适位置，维护堆 shiftDown(1); return max; } private void shiftDown(int i) { //定义左孩子，完全二叉树如果有孩子，一定有左孩子 while (2*i<=count) { int j=2*i; //j+1即为右孩子 if(j+1<=count&&data[j+1]>data[j]) j+=1; if(data[i]>=data[j]) break; swap(i, j); i=j; } } private void swap(int i, int j) { if(i!=j) { int temp=data[i]; data[i]=data[j]; data[j]=temp; } } public void print(int []data,int count) { for(int i=0;i<=count;i++) System.out.print(data[i]+" "); System.out.println(); }//测试这里写代码片
public static void main(String args[]) { //创建堆 MaxHeap maxHeap =new MaxHeap(100); //向堆中存，插入元素，入队 for(int i=0;i<20;i++) { maxHeap.insert((int)(Math.random()*100)); } maxHeap.print(data,maxHeap.count); System.out.println(maxHeap.size()); //从堆里取，依次取出最大值，从大到小 while(!maxHeap.isEmpty()) { System.out.print(maxHeap.extractMax()+" "); } } }/** *实现堆排序 *时间复杂度为O(nlogn) *空间复杂度O（n） *根节点从1开始，左孩子：2i，右孩子2i+1; */
public class HeapSort1 { public void heapSort1(int[]arr,int n) { MaxHeap heap1=new MaxHeap(n); //存入堆 //这一步可以优化，不用每一个元素都要insert一次 for(int i=0;i<n;i++) { heap1.insert(arr[i]); } //从小到大排序 for(int i=n-1;i>=0;i--) { arr[i]=heap1.extractMax(); } } public static void main(String[] args) { int [] arr= {8,7,4,5,9,2,10,3,3,3,30,3}; int n=arr.length; HeapSort1 sort1=new HeapSort1(); sort1.heapSort1(arr, n); for(int i=0;i<n;i++) System.out.print(arr[i]+" "); } }