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)