/**

 * @author Dkx

 * @version 1.0

 * @2024/1/2211:08

 * @function

 * @comment

 * 大顶堆

 */

public class MaxHeap

{

    int array[];

    int size;

    /**

     * 如果实例化对象时传入的是一个普通数组那么我们就需要 进行 建堆 让这个数组符合 大顶堆的 特性

     * @param array

     */

    public MaxHeap(int array[])

    {

        // 将用户传入的 数组 赋值到 成员变量中的数组

        this.array = array;

        // 更新数组的大小

        this.size = array.length;

        // 调用 建堆 方法进行建堆

        heapify();

    }

    // 建堆

    private void heapify()

    {

        // 如何找到最后这个非叶子节点 size / 2 - 1

        for(var i = size / 2; i >= 0; i--)

            down(i);

    }

    // 将 parent 索引处的元素下潜：与两个孩子较大者交换，直至没孩子或孩子没它大

    public void down(int parent)

    {

        // 通过公式 获取 当前节点的 左孩子

        int left = parent * 2 + 1;

        // 通过上面公式 + 1 获取当前节点的 右孩子

        int right = left + 1;

        // 假设 当前节点 是较大值

        int max = parent;

        // 在左孩子 在合法索引范围内 判断 父节点的值 是否小于 左孩子，如果小就将左孩子的索引值赋值给 max 记录

        if(left < size && array[max] < array[left])

            max = left;

        // 在右孩子 在合法索引范围内 判断 父节点的值 是否小于 右孩子，如果小就将右孩子的索引值赋值给 max 记录

        if(right < size && array[max] < array[right])

            max = right;

        // 如果上面两个判断中 有一个满足了 说明 父节点不是最大值

        // 如果 max 被更改那么就不等于 parent 了 说明右需要交换位置的

        if(max != parent)

        {

            // 让 父节点 和 它 左右孩子 值 较大的 那个进行交换位置

            swap(max, parent);

            // 递归 传入 max 也就是当前父节点的位置 继续下一轮的判断

            down(max);

        }

    }

    // 交换两个索引处的元素

    public void swap(int i, int j)

    {

        int t = array[i];

        array[i]  = array[j];

        array[j] = t;

    }

}

@Test

public void test()

{

   // 定义一个数组

   int array[] = {2, 3, 1, 7, 6, 4, 5};

   // 将数组传入 MaxHeap 对象的构造函数中，这个构造函数中 实现了 heapify 方法来对数组进行 堆化处理了

   MaxHeap maxHeap = new MaxHeap(array);

   System.out.println("排序前：" + Arrays.toString(maxHeap.array));

   // 循环到 堆 里 只有一个元素 还没做操作为止

   while(maxHeap.size > 1)

   {

      // 每次都让 堆顶元素 和 堆低元素进行交换位置

      maxHeap.swap(0, maxHeap.size - 1);

      // 每次 交换位置后 让 堆的 大小 缩小 1

      maxHeap.size--;

      // 让 堆顶元素 下潜 找到自己合适的位置 重新符合 大顶堆的特性

      maxHeap.down(0);

   }

   System.out.println("排序后：" + Arrays.toString(maxHeap.array));

}