package com.wschase.heap;

/**二叉堆（逻辑上是完全二叉树）——解决最值问题
 * Author:WSChase
 * Created:2019/4/10
 */

/**
 * 对于堆我们需要知道几个它的子节点和父节点之间的关系：
 * （1）若i>0,双亲序号：（i-1）/2
 *       i=0,i为根节点编号，无双亲结点
 * （2）2i+1<n,左孩子序号为2i+1,否则无左孩子
 * （3）2i+2<n,右孩子序号为2i+2,否则无有孩子
 *
 * 再者堆是存放在一个顺序表里面，它是按照层序遍历来实现的
 * 其中堆又分为大堆和小堆。
 */
class Heap{
    //我们定义一个静态顺序表
    int[] array=new int[100];
    int size;

}
public class Solution {
    /**
     * 1.建堆
     * 乱序数组——>建堆——>满足堆的性质
     * 下面实现的是建大堆
     */
    public void heapInit(Heap ph,int[] source,int size){
        for(int i=0;i<size;i++){
            ph.array[i]=source[i];
        }
        ph.size=size;
    }

    public void heapMakeHeap(Heap ph){
        //父节点的最小值到最大值
        for(int i=(ph.size-2)/2;i>=0;i--){
            heapAdjustDown(ph,i);
        }
    }

    //向下调整
    private void heapAdjustDown(Heap ph, int root) {
        //叶子结点判断：判断孩子的下标是否越界：只要判断左孩子就可以了
        int left = root * 2+1;//这个是左孩子的下标
        if(left>=ph.size){
            return;
        }
        //一定有左孩子
        int maxChild=left;
        //右孩子存在并且右孩子的值大于左孩子的值，这个时候的最大孩子结点的值就需要改变
        if(2*root+2<ph.size&&ph.array[2*root+2]>ph.array[left]){
            maxChild=2*root+2;
        }
        if(ph.array[root]>ph.array[maxChild]){
            return;
        }
        int t=ph.array[root];
        ph.array[root]=ph.array[maxChild];
        ph.array[maxChild]=t;

        heapAdjustDown(ph,maxChild);
    }

    /**
     * 2.删除堆
     */
    public void heapPop(Heap ph){
        ph.array[0]=ph.array[ph.size-1];
        ph.size--;

        heapAdjustDown(ph,0);
    }
    public int heapTop(Heap ph){
        return ph.array[0];
    }
    public void heapAdjustUp(Heap ph,int child){
        int parent;
        while(child>0){
            parent=(child-1)/2;
            if(ph.array[parent]>=ph.array[child]){
                return;
            }
            swap(ph.array[parent],ph.array[child]);
            child=parent;
        }
    }

    private void swap(int i, int i1) {
        int temp=i;
        i=i1;
        i1=temp;
    }

    /**
     * 3.选择排序：一次找到未排序空间中的最大值交换最大值到空间后
     * 注意：
     * 从小到大排序：选择最大堆
     * 从大到小排序：选择最小堆
     */
    public void heapSort(int[] array,int size){
        //建大堆
        for(int i=(size-2)/2;i>=0;i--){
            arrayAdjustDown(array,size,i);
        }
        for(int j=0;j<size;j++){
            int s=size-1-j;
            swap(array[0],array[s]);
            arrayAdjustDown(array,size-1-j,0);
        }
    }

    private void arrayAdjustDown(int[] array, int size, int i) {
    }

}