如何在O(N)时间内实现用链表创建左式堆?

Question

我的想法是把N个元素以二叉树节点的形式保存在数组中, 然后就和在数组中创建二叉堆的过程一样了, 只是在上滤和下滤的过程中维持链表的结构. 除此之外还有什么其他的方法吗?

Answer 1

设已经生成的链表每个元素就是二叉堆中的节点（数据结构中包含左右子叶的指针，但子叶尚未赋值）

设两个指针P1 = Head、P2 = Head，及深度变量Deep = 1，步进计数Step = 1，并进行如下方式扫描

P1 ->
P2 ->
01 02 03 04 05 06 07 08 09 10 ...

当 Step = Deep 时
    P2 向前移动 Deep ^ 2 个节点
    Deep += 1
    Step = 0
否则
    将 P2 节点赋值给 P1 左叶
    P2 ++
    将 P2 节点赋值给 P1 右叶
    P2 ++
    P1 ++
    Step ++
    
执行上述过程循环至 P2 到达链表尾

Answer 2

书上的课后习题提供了另外一种更高效的方法, 就是通过使用一个队列, 不断从队列中取出两个堆进行合并, 直至队列中只剩下一个堆为止, 这种方法形成的堆是左式堆.

//课后的解法, 效率高, 不需要额外的空间
public static LeftHeap create1(int[] num)
{
    if(num == null || num.length < 1)
        return null ;
    Queue<LeftHeap> queue = new LinkedList<>() ;
    for(int i=0 ; i<num.length ; i++)
    {
        queue.add(new LeftHeap(num[i] , 0)) ;
    }

    while (queue.size()>=2)
    {
        LeftHeap h1 = queue.poll() ;
        LeftHeap h2 = queue.poll() ;

        LeftHeap heap = merge(h1 , h2) ;
        queue.add(heap) ;
    }

    return queue.poll() ;
}
//我自己思路写的
public static LeftHeap create2(int[] num)
{
    if(num == null || num.length < 1)
        return null ;
    int N = num.length ;
    LeftHeap[] arr = new LeftHeap[N+1] ;
    for(int i=0 ; i<N ; i++)
    {
        arr[i+1] = new LeftHeap(num[i] , 0) ;
    }

    for(int k=N/2 ; k>=1 ; k--)
        sink(arr , k , N) ;
    return arr[1] ;
}

private static void sink(LeftHeap[] heap , int k , int N)
{
    while (k*2 <= N)
    {
        int min = k*2 ;
        heap[k].left = heap[min] ;
        if(min+1 <= N)
        {
            heap[k].right = heap[min+1] ;
            heap[k].npl = heap[min+1].npl+1 ;
            if(heap[min].num > heap[min+1].num)
                min++ ;
        }

        if(heap[k].num > heap[min].num)
        {
            int temp = heap[k].num ;
            heap[k].num = heap[min].num ;
            heap[min].num = temp ;
            k=min ;
        }
        else
            break ;
    }
}