1.堆的两个性质

1.1 结构性质

堆是一棵完全填满的二叉树，可能出现的例外在底层，底层从左到右填充。

一棵完全二叉树.png 完全二叉树的节点数.png

因为完全二叉树很有规律，所以可以使用数组来表示
对于数组中i位置的元素，它的左子节点在2i上，右子节点在(2i+1)上，父节点在(i/2)上，

完全二叉树的数组实现.png

1.2 堆序性质

让操作快速执行的是堆序性质，由于我们想快速的找出最小元，所以最小云应该放到根上，如果任意子树也是堆，那么所有节点都小于他的后裔。
堆序性质：X中的关键字小于等于X的父节点中的关键字（根节点除外）

堆序性质.png

2.堆的基本操作

2.1insert

第一步：在下一个可用位置创建一个空穴（保证结构性）
第二步：1.如果x可以放入空穴(可以是指不破坏堆序性质)，那么插入完成
2.否则，就把空穴父节点上的元素移入空穴，也就是空穴朝着根的方向冒一步，继续该过程，知道x能被放入空穴

insert.png insert过程.png

    public void insert(AnyType x){
        if(currentSize == array.length-1)
            enlargeArr(array.length*2+1);
        int hole = ++currentSize;
        for(;hole>1;&&x.compareTo(array[hole/2])<0;hole/=2){
            array[hole] = array[hole/2];
        }
        array[hole] = x;
    }

2.2deleteMin删除最小元

第一步：删除最小元在根节点处建立一个空穴，将堆中最后一个元素放入这个空穴（保证结构性）
第二步：如果x满足堆序性，完成
否则，空穴的两个儿子的较小者移入空穴，这样就把空穴下推了一层，重复这个步骤直到满足堆序性质

deletemin的过程.png

    public AnyType deleteMin(){
        if(isEmpty())
            throw new IndexOutOfBoundsException();
        AnyType minItem = findMin();
        array[1] = array[currentSize--];//将最后一个元素放入第一个位置
        percolateDown(1);//从第一个位置开始下沉操作
        return minItem;
    }
    
    
    private void percolateDown(int hole){
        int child;
        AnyType tmp = array[hole];
        for(;hole*2<currentSize;hole=child){
            child = hole*2;
            if(child!=currentSize&&
                    array[child+1].compareTo(array[child])<0)
                child++;//找出两个子中的较小者
            if(array[child].compareTo(array[hole])<0)
                array[hole] = array[child];
            else
                break; 
        }
        array[hole] = tmp;
    }

2.3构建堆buildHeap

buildHeap构建堆1.png buildHeap构建堆2.png

    private static final int DEFAULT_CAPACITY = 10;
    private int currentSize ;
    private AnyType[] array;
    
     
    public BinaryHeap(AnyType[] items){
        currentSize = items.length;
        array = (AnyType[])new Comparable[(currentSize+2)*11/10];
        int i =1;
        for(AnyType item:items)
            array[i++] = item;
        buildHeap();
    } 
    
    
    private void buildHeap(){
        for(int i=currentSize/2;i>0;i--)
            percolateDown(i);
    }
    
    
    private void percolateDown(int hole){
        int child;
        AnyType tmp = array[hole];
        for(;hole*2<currentSize;hole=child){
            child = hole*2;
            if(child!=currentSize&&
                    array[child+1].compareTo(array[child])<0)
                child++;//找出两个子中的较小者
            if(array[child].compareTo(array[hole])<0)
                array[hole] = array[child];
            else
                break; 
        }
        array[hole] = tmp;
    }

3.堆排序

    private static int leftChild(int i){
        return 2*i +1;
    }
    
    private static <AnyType extends Comparable<? super AnyType>>
    void percDown(AnyType[] a,int i,int n){
        int child;
        AnyType tmp;
        for(tmp=a[i];leftChild(i)<n;i=child){
            child = leftChild(i);
            if(child!=n-1&&a[child].compareTo(a[child+1])<0){
                child++;
            }
            if(tmp.compareTo(a[child])<0){
                a[i] = a[child];
            }else
                break;
            
        }
        a[i]= tmp;
    }
    
    
    
    public static <AnyType extends Comparable<? super AnyType>>
    void heapSort(AnyType[] a){
        for(int i=a.length/2;i>=0;i--){
            percDown(a, i, a.length);
        }
        for(int i=a.length-1;i>0;i--){
            swapReference(a,0,i);
            percDown(a, 0, i);
        }
    }