堆排序

public class Heap{
        int cap;
        int count;
        int [] data;
        public Heap(int cap){
            this.cap = cap;
            this.count = 0;
            data = new int[cap + 1];
        }

        private void swap(int [] arr, int i, int j){
               int temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
        }

        private void shiftUp(int k){
            while( k > 1 && data[k/2] < data[k]){
                swap(data,k/2,k);
                 k = k/2;
            }
        }

        public void insert(int num){
            data[++count] = num;
            shiftUp(count);
        }


        public int delete(){
            int res = data[1];
            swap(data,1,count);
            count--;
            shiftDown(1);
            return res;
        }

        private void shiftDown(int k){
            while( 2*k <= count){
                int j = 2 * k;
                if(2 * k + 1 <= count && data[2 * k + 1] > data[2 * k]){
                    j = 2 * k + 1;
                }
                if(data[k] >= data[j]) break;
                swap(data,k,j);
                k = j;
            }
        }

//           1
//        2    3
//      4   5


        public void heapify(){
            int i = count / 2; // first not leaf node
            while (i >= 1){
                shiftDown(i--);
            }
        }


    public static void main(String[] args) {
            Heap heap = new Heap(20);
            for (int i = 0; i < 20; i++){
                  heap.data[i+1] =new Random().nextInt(100);
            }
            heap.count = 20;
            heap.heapify();

            for (int i = 0; i < 20;i++ ){
                System.out.println(heap.delete());
            }

    }

    }