堆的构建和堆排序

二叉堆

特征：任何一个子节点都不大于它的父节点；

堆是一个完全的二叉树
除了最后一层外，其他层都必须是完全的
在最后一层子节点必须集中在左侧

最大堆
左右子节点都小于父节点
用数组存储二叉堆

• 每个左结点的序号是父节点的2倍；
• 每个右结点的序号是父节点的2倍加1；

public class MaxHeap {
    private int[] data;
    private int count;//元素个数
    private int capacity; //数组容量

    public MaxHeap(int capacity){
        data=new int[capacity+1];
        count=0;
        this.capacity=capacity;
    }

    public int size(){
        return count;
    }
    public boolean isEmpty(){
        return count==0;
    }

    private void swap(int datum, int datum1) {

        int t=data[datum];
        data[datum]=data[datum1];
        data[datum1]=t;
    }

    public void insert(int ele){

        assert count+1<=capacity; //判断是否越界
      data[count+1]=ele;
      shiftUp(count+1);
      count++;

    }

    //给新添加的元素寻找合适的位置
    private void shiftUp(int key) {
        //如果新元素大于父节点的元素 则交换位置
        while (key>1&&data[key/2]<data[key]){
            swap(key/2,key);
            key/=2;
        }
    }

    //从堆中取出一个元素  取出堆顶的元素
    //1.先把堆顶的元素取出来；
    //2. 把最低层最右边的元素放到堆顶的位置
    //3. 重新构建最大堆
    public int extractMax(){
        assert count>0; //判断不为空
        int tmp=data[1];
        swap(1,count);
        count--;
        shiftDown(1);
        return tmp;
    }

    private void shiftDown(int key) {

        //判断是否有左孩子
        while (2*key<=count){
            //如果只有左孩子则跟左孩子交换位置
            //如果也有右孩子，则左右孩子比较，跟大的那个交换位置
            int j=2*key;
            if(j+1<=count&&data[j+1]>data[j]){
                    j=j+1;
            }
            //如果父节点大于子节点  则不用交换
            if(data[key]>=data[j]){
                break;
            }
            swap(key,j);
            key=j;
            }

        }
    }

将数组构建成堆

利用特性： 对于第一个非叶子节点的序号是第一个叶子节点序号的0.5倍;

重载最大堆的构造方法

heapify

  //重载构造函数 用来将数组构建成堆
    public  MaxHeap(int[] array,int n){
        data=new int[n+1];
        capacity=n;
        for (int i = 0; i < n; i++) {
            data[i+1]=array[i];
        }
        count=n;
        //从第一个非叶子节点开始  将每个节点都构建成满足堆特性
        for (int i=count/2;i>=1;i--){
            shiftDown(i);
        }
    }

堆排序

public static int[] heapSort(int[] array){

        MaxHeap mh = new MaxHeap(array, array.length);
        //再每次取出最大的元素放入数组  从小到大遍历
        for (int i=array.length-1;i>=0;i--){
            array[i]=mh.extractMax();
        }

        return array;
    }

总结
将n个元素逐一插入到空堆中，算法复杂度是O(nlogn),
heapify的过程，算法复杂度为O(n)

原地堆排序

将数组堆化后 ，开始进行原地排序，就是不申请额外的空间。

描述：将数组转化为最大堆，每次将最后的叶子节点和根节点交换位置，再进行最大堆化。

public  int[] heapSort(int[] array,int n){
        //将数组 heapify (堆化)
        for (int i = (n-1)/2; i >0; i--) {
            shiftDown(array,n,i);
        }
        
        for (int i=n-1;i>0;i--){
            swap(array,0,i);
            shiftDown(array,i,0);
        }
        return array;

    }
    private void swap(int[] data,int datum, int datum1) {

        int t=data[datum];
        data[datum]=data[datum1];
        data[datum1]=t;
    }

    private  void shiftDown(int[] array, int n, int key) {
        while (2*key+1<n){
            int j=2*key+1; //左孩子
            //如果有右孩子并且右孩子大于左孩子  则交换key和右孩子的位置
            if(j+1<n&&array[j]<array[j+1]){
                j+=1;
            }
            //如果父节点 大于孩子中比较大的那个值 则不用交换
            if(array[key]>=array[j]){
                break;
            }
            swap(array,key,j);
            key=j;
        }
    }

排序算法总结

索引堆 index heap

比较的是data，交换的是index。