// 小顶堆

public class MinHeap

{

    ListNode[] array;

    int size;

    public MinHeap(int capacity)

    {

        array = new ListNode[capacity];

    }

    public boolean offer(ListNode e)

    {

        // 判断堆中是否 满了

        if(isFull())

            return false;

        // 获取 最后一个元素

        int child = size++;

        // 通过公式 得出 当前元素的 父节点

        int parent = (child - 1) / 2;

        // 如果 不是 root 节点 和 当前的元素值 小于 父节点的元素值 就满足条件

        while(child > 0 && e.val < array[parent].val)

        {

            // 将 父节点的 元素值 赋值给 当前元素

            array[child] = array[parent];

            // 将 父节点的索引位置 赋值到 当前索引

            child = parent;

            // 再次计算 当前 节点的 父节点的索引位置

            parent = (child - 1) / 2;

        }

        // 将 当前的 元素赋值 到 当前节点中

        array[child] = e;

        return true;

    }

    public ListNode poll()

    {

        // 判断 堆中是否为空

        if(isEmpty())

            return null;

        // 将 root 节点 与 最后一个节点 交换位置 ，方便移除 提高效率

        swap(0, size - 1);

        // 大小 减一

        size--;

        // 拿到 最后 的值

        ListNode e = array[size];

        // 将最后的 值赋值为 null 交给 GC 垃圾回收处理

        array[size] = null;

        // 将 当前的 root 节点 向下比较 找到自己合适的位置

        down(0);

        return e;

    }

    private void swap(int i, int j)

    {

        // 经典的位置交换

        ListNode t = array[i];

        array[i] = array[j];

        array[j] = t;

    }

    private void down(int parent)

    {

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

        int left = 2 * parent + 1;

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

        int right = left + 1;

        // 将当前 节点 假定为 最小的 元素 赋值给 min

        int min = parent;

        // 判断 如果 left 没有超出 索引范围 并且 left 所在的 值 比 min 所在的值 还要小

        if(left < size && array[left].val < array[min].val)

            // 就将 left 索引赋值给 min

            min = left;

        // 与上面判断同理

        if(right < size && array[right].val < array[min].val)

            min = right;

        // 判断如果 min 不等于 parent 说明上面是有符合交换条件的 就执行 if 方法体

        if(min != parent)

        {

            // 交换位置

            swap(min, parent);

            // 将当前的 min 进行递归调用 重复这个 工作 直到 该 值 找到自己合适的位置即可

            down(min);

        }

    }

    public boolean isEmpty()

    {

        return size == 0;

    }

    public boolean isFull()

    {

        return size == array.length;

    }

}

/**

 * Leetcode 很多链表题目用到的节点类

 */

public class ListNode {

    public int val;

    public ListNode next;

    public ListNode(int val, ListNode next) {

        this.val = val;

        this.next = next;

    }

    @Override

    public String toString() {

        StringBuilder sb = new StringBuilder(64);

        sb.append("[");

        ListNode p = this;

        while (p != null) {

            sb.append(p.val);

            if (p.next != null) {

                sb.append(",");

            }

            p = p.next;

        }

        sb.append("]");

        return sb.toString();

//        return String.valueOf(this.val);

    }

    public static ListNode of(int... elements) {

        if (elements.length == 0) {

            return null;

        }

        ListNode p = null;

        for (int i = elements.length - 1; i >= 0; i--) {

            p = new ListNode(elements[i], p);

        }

        return p;

    }

}

public class DemoTest

{

    // 合并多个有序链表

    private ListNode merge(ListNode[] list)

    {

        MinHeap heap = new MinHeap(list.length);

        // 1. 将链表的头节点 添加到 小顶堆中

        for (ListNode h : list)

        {

            if(h != null)

            {

                heap.offer(h);

            }

        }

        // 2. 不断从堆顶移除最小元素，加入新链表

        ListNode s = new ListNode(-1, null);

        // 定义辅助变量

        ListNode t = s;

        // 判断如果 heap 对象不为空

        while(! heap.isEmpty())

        {

            // 从 heap 堆中 弹出 顶部 元素

            ListNode min = heap.poll();

            // 将 min 节点 添加到 t 链表中

            t.next = min;

            // 更新 t 节点

            t = min;

            if(min.next != null)

                // 将 上面 poll 处的 min 的 next 节点 在 添加到 heap 对象中这样就起到了 向后指向的 作用

                heap.offer(min.next);

        }

        //s.next 返回 除了 哨兵节点外的 其它元素

        return s.next;

    }

    public static void main(String[] args)

    {

        ListNode[] list = {

                ListNode.of(1, 4, 5),

                ListNode.of(1, 3, 5),

                ListNode.of(2, 6),

                null,

        };

        System.out.println(new DemoTest().merge(list));

    }

}