public class MaxHeap {private int[] data;private int count;private int capacity;public MaxHeap(int capacity){this.capacity=capacity;data=new int[capacity+1];count=0; }public void insert(int n) {data[++count]=n; shiftUp(count); }private void shiftUp(int n) {while(n>1&&data[n/2]<data[n]) { swap(data,n/2,n); n=n/2; } }public int size(){return count; }public boolean isEmpty(){return count==0; }public int getMax()//复制一个最大值 {assert (count>0);return data[1]; }public int extractMax()//直接将最大值取出来了，堆里面没有了 {assert(count-1>0);int max=data[1]; swap(data,count,1);count--; shiftDown(1);return max; }private void shiftDown(int i) {int j=i*2; //找出左节点 while(j<=count) //如果存在子节点，就要继续往下走，不论是否存在右节点 {if(j+1<=count&&data[j+1]>data[j]) //如果存在右节点，比较左右节点 {if(data[j+1]>data[i]) { swap(data, i, j + 1); i = j + 1; j = 2 * i; }else break; }else {if(data[j]>data[i]) { swap(data,i,j); i=j; j=2*i; }else break; } } }public void swap(int[] arr,int l,int r) {int temp=arr[l]; arr[l]=arr[r]; arr[r]=temp; }public static void main(String[] args) { MaxHeap maxHeap=new MaxHeap(100);int N=100;int M=100;for(int i=1;i<=100;i++) { maxHeap.insert((int) (Math.random()*M)); }int[] arr=new int[N];for(int i=0;i<N;i++) { arr[i]=maxHeap.extractMax(); }for (int i = 0; i <N ; i++) { System.out.println(arr[i]); } }}
转载于:https://www.cnblogs.com/cold-windy/p/11199768.html
相关资源：各显卡算力对照表！
