最大堆

最大堆

• 二叉堆是一颗完全二叉树(把元素顺序排列成树的形状)
• 堆中的某个节点的值总是不大于其父节点的值

最大堆的实现

public class MaxHeap<E extends Comparable<E>>{
    
    private Array<E> data;

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data = new Array<>();
    }

    // O(n)
    // Heapify:将数组整理成堆
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        for(int i=parent(arr.length-1);i>=0;i--){
            siftDown(i);
        }
    }

    public int getSize(){
        return data.getSize();
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }

    private int parent(int index){
        if(index==0){
            throw new IllegalArgumentException("param is illegal");
        }
        return (index-1)/2;
    }

    private int leftChild(int index){
        return index*2+1;
    }

    private int rightChild(int index){
        return index*2+2;
    }

    // O(logn)
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize()-1);
    }

    private void siftUp(int k){
        while(k>0&&data.get(parent(k)).compareTo(data.get(k))<0){
            data.swap(k,parent(k));
        }
    }

    // 取出堆中最大的元素
    // O(logn)
    public E extractMax(){
        E ret = findMax();
        
        data.swap(0,data.getSize()-1);
        data.removeLast();
        siftDown(0);

        return ret;
    }

    private void siftDown(int k){
        while(leftChild(k)<data.getSize()){
            int j = leftChild(k);
            if(j+1<data.getSize()&&data.get(j+1).compareTo(data.get(j))>0){
                j++;
            }
            if(data.get(k).compareTo(data.get(j))>=0){
                break;
            }
            data.swap(k,j);
        }
    }

    public E findMax(){
        if(data.isEmpty()){
            return null;
        }
        return data.get(0);
    }

    public E replace(E e){
        E ret=findMax();
        
        data.set(0,e);
        siftDown(0);

        return ret;
    }
}

堆排序

public static <E extends Comparable<E>> void sort(E[] data){
    if(data.length<=1){
        return;
    }
    for(int i=(data.length-2)/2;i>=0;i--){
        siftDown(data,i,data.length);
    }
    for(int i=data.length-1;i>=0;i--){
        swap(data,0,i);
        siftDown(data,0,i);
    }
}

private static <E extends Comparable<E>> void siftDown(E[] data,int k,int n){
    while(2*k+1<n){
        int j=2*k+1;
        if(j+1<n&&data[j+1].compareTo(data[j])>0){
            j++;
        }
        if(data[k].compareTo(data[j])>=0){
            break;
        }
        swap(data,k,j);
        k=j;
    }
}

private static <E> void swap(E[] arr,int i,int j){
    E t=arr[i];
    arr[i]=arr[j];
    arr[j]=t;
}