23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

参考资料

https://www.cnblogs.com/zywscq/p/5403051.html
https://www.cnblogs.com/skysand/p/4300711.html

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int value;
    struct node *next;
}node; 

struct heap {
    int ele;
    struct node *head;
};

node **generateList(int (*data)[6], int row, int column);
void displayList(node **head, int row);
void heapsort(struct heap *heap);
void makeHeap(struct heap *heap);
void siftDown(struct heap *heap, int i, int len);

int main()
{
    int i,j;
    int data[][6] = {{1,2,21,47},
                     {15,60,65,84},
                     {77,88,93,100},
                     {5,8,17,36},
                     {20,24,63,72}};
    int *merged = (int *)malloc(sizeof(data));
    int row = sizeof(data)/sizeof(data[0]);
    int column = sizeof(data[0])/sizeof(data[0][0]);
    struct heap *h = (struct heap *)malloc(sizeof(struct heap)*(row+1));

    node **head;

    head = generateList(data,row,column);
    displayList(head,row);

    h[0].ele = row;
    h[0].head = NULL;
    for(i = 0; i < row; i++)
    {
        h[i+1].ele = head[i]->value;
        h[i+1].head = head[i];
    }
    heapsort(h);

    i = 0;
    while(1)
    {
        if(h[0].ele == 0) break;

        merged[i++] = h[1].ele;
        if(h[1].head->next != NULL)
        {
            h[1].head = h[1].head->next;
            h[1].ele = h[1].head->value;
        }
        else
        {
            h[1] = h[h[0].ele];
            h[0].ele--;
        }
        heapsort(h);
        
    }

    printf("合并后数组：");
    for(j = 0; j < i; j++)
    {
        printf("%d ",merged[j]);
    }
    printf("\n");

    return 0;
}

/*
 * 生成链表
 * @param data 二维数组
 * @param row 行数
 * @param column 列数
 */
node **generateList(int (*data)[6], int row, int column)
{
    int i,j;
    node **head = (node **)malloc(sizeof(node *)*row);
    node **tail = (node **)malloc(sizeof(node *)*row);
    
    for(i = 0; i < row; i++)
    {
        tail[i] = (node *)malloc(sizeof(node));
        head[i] = tail[i];
        for(j = 0; j < column; j++)
        {
            if(data[i][j] != 0)
            {
                tail[i]->value = data[i][j];
                if(data[i][j+1] != 0)
                {
                    tail[i]->next = (node *)malloc(sizeof(node));
                    tail[i] = tail[i]->next;
                }
                else
                {
                    tail[i]->next = NULL;
                }
            }
        }
    }
    
    return head;
}

void displayList(node **head, int row)
{
    int i;
    node *cur;

    for(i = 0; i < row; i++)
    {
        cur = head[i];
        while(cur != NULL)
        {
            printf("%d ",cur->value);
            cur = cur->next;
        }
        printf("\n");
    }
}

void heapsort(struct heap *heap)
{
    int len = heap[0].ele;
    int i;
    struct heap temp;
    
    makeHeap(heap);
    
    i = len;
    while(i > 1)
    {
        temp = heap[1];
        heap[1] = heap[i];
        heap[i] = temp;
        i--;

        siftDown(heap,1,i);
    }
}

void makeHeap(struct heap *heap)
{
    int len = heap[0].ele;
    int i;

    for(i = len/2; i >= 1; i--)
    {
        siftDown(heap, i, len);
    }
}

/*
 * 使父节点的值大于其子节点的值
 * @param heap 堆地址
 * @param i 节点索引
 * @param len 长度
 */
void siftDown(struct heap *heap, int i, int len)
{
    struct heap temp;

    if(i < 1 || 2*i > len) return;

    temp = heap[i];
    while(2*i <= len)
    {
        i *= 2;
        if((i < len) && (heap[i].ele < heap[i+1].ele))
        {
            i += 1;//找出子节点中的较大者
        }

        if(temp.ele >= heap[i].ele)
        {
            i /= 2;
            break;
        }

        heap[i/2] = heap[i];
    }
    heap[i] = temp;
}