The heap sort is useful to get min/max item as well as sorting. We can build a tree to a min heap or max heap. A max heap, for instance, keeps a parent being not smaller than children.
The following code is for a max heap. The top indicates the next insertion position in the array which is identical to the array size.
class Heap { private int[] arr; private int top; public Heap(int sz) { arr=new int[sz]; top=0; } public void push(int num) { arr[++top]=num; climbUp(top); } public void pop() { int min=arr[1]; arr[1]=arr[top--]; climbDown(1); arr[top+1]=min; } public int size() { return top; } private void climbUp(int p) { if(p<=1||arr[p]<=arr[p/2]) return; swapAt(p,p/2); climbUp(p/2); } private void climbDown(int p) { int np=p*2; if(np>top) return; if(np<top&&arr[np+1]>arr[np]) np++; if(arr[p]>=arr[np]) return; swapAt(p,np); climbDown(np); } private void swapAt(int p,int q) { int t=arr[p]; arr[p]=arr[q]; arr[q]=t; } } 
Top comments (0)