MinHeap.java

public class MinHeap implements Heap{

    private int[] Heap;
    private int size;
    private int n;

    public MinHeap(int[] heap,int num,int max){
        Heap = heap;
        n = num;
        size = max;
        buildheap();
    }

    public MinHeap(int max){
        this.size = max;
        n = 0;
        Heap = new int[max];
    }
    @Override
    public int heapsize() {
        return size;
    }

    @Override
    public boolean isLeaf(int pos) {
        return (pos>=n/2)&&(pos<n);
    }

    @Override
    public int left(int pos) {
        if(pos<n/2){
            return 2 * pos +1;
        }
        return -1;
    }

    @Override
    public int right(int pos) {
        if(pos<(n-1)/2){
            return 2 * pos + 2;
        }

        return -1;
    }

    @Override
    public int parent(int pos) {
        if(pos>0){
            return (pos-1)/2;
        }
        return -1;
    }

    @Override
    public void insert(int val) {
        if(n< size){
            int curr = n++;
            Heap[curr] = val;
            while(curr != 0 && Heap[curr]<Heap[parent(curr)]){
                swap(Heap,curr,parent(curr));
                curr = parent(curr);
            }
        }
        else{
            System.out.println("The Heap is Full");
        }
    }

    @Override
    public int delete() {
        if(n<=0){
            System.out.println("The heap is Empty");
            return -1;
        }

        else{
            swap(Heap,0,--n);
            if(n!=0){
                siftdown(0);
            }
            return Heap[n];
        }
    }

    @Override
    public void siftdown(int pos) {
        if(pos>=0 && pos<n){
            while(!isLeaf(pos)){
                int j = left(pos); //获得pos的左儿子位置
                if(j<n-1 && Heap[j]>Heap[j+1]){
                        j++;      //现在Heap[j]是左右儿子更小的那个
                }

                if(Heap[pos]<=Heap[j])return;
                swap(Heap,pos,j);
                pos = j;
            }
        }
    }

    public static void swap(int[] Heap,int i,int j){
        int temp = Heap[i];
        Heap[i] = Heap[j];
        Heap[j] = temp;
    }

    public void buildheap(){
        for(int i = n/2-1;i>=0;i--){
            siftdown(i);
        }
    }

    public int getMin(){
        return Heap[0];
    }


    public static void HeapSort(int[] nums,int start,int end){
        MinHeap heap = new MinHeap(nums,nums.length,nums.length);
        heap.buildheap();
        for(int i = 0;i<nums.length;i++){
            if(i>=start && i<=end){
                System.out.printf("%d  ",heap.getMin());
            }
            heap.delete();
        }
    }
    public static void main(String[] args){
        int[] nums = {10,99,100,11,17,19,33,81,12,5,52,63,1};
        HeapSort(nums,0,12);
    }

}