java实现数据结构-堆

java实现数据结构-堆

堆是一个完全二叉树，其中每个节点的值总是大于等于子节点的值。一般来说，我们用一个数组而不是用指针建立一个树。这是由于堆是完全二叉树，当数组表示时,位置i 的节点的父节点位置一定为i/2，而它的两个子节点的位置又一定分别为2i 和2i+1，因此可以很方便的进行上浮和下沉 *** 作。

                                                         图1  堆(最大堆)

基于此，实现的代码如下：

public class Heap> {
    List heap = new ArrayList<>();

    public E top(){
        return heap.get(0);
    }

    public void push(E k){
        heap.add(k);
        swim(heap.size()-1);
    }

    //最后一个数挪到开头，然后下沉
    public void pop(){
        heap.set(0,heap.remove(heap.size()-1));
        sink(0);
    }

    //上浮
    public void  swim(int pos){
        while(pos>=1 && heap.get(pos/2).compareTo(heap.get(pos))<0){
            swap(pos/2,pos);
            pos = pos/2;
        }
    }

    //下沉
    public void sink(int pos){
        int N = heap.size()-1;
        while(2*pos<=N){
            int i = 2*pos;
            if(i=0) break;
            swap(pos,i);
            pos = i;
        }
    }

    private void swap(int i,int j){
        if(i==j) return;
        E temp = heap.get(i);
        heap.set(i,heap.get(j));
        heap.set(j,temp);
    }
}