Heap Sort

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;
        }
    }

Blog

drevispas

Join Our Newsletter. No Spam, Only the good stuff.

Related