/*
* 请给出一个时间为O(nlgk),用来将k个已排序链表合并为一个排序链表的算法。
* 此处n为所有输入链表中元素的总数。（提示：用一个最小堆来做k路合并）
*
* 思路：利用有k个元素的最小堆有lgk的复杂度，
* 所以堆的元素组成要每个链表的一个元素组成
*
* 具体步骤：
*step1：取每个链表的第一个元素，构造成一个含有k个元素的堆
*step2：把根结点的值记入排序结果中。
*step3：判断根结点所在的链表，若该链表为空，则go to step4，否则go to step5
*step4：删除根结点，调整堆，go to step2
*step5：把根结点替换为原根结点所在链表中的第一个元素，调整堆，go to step 2
*/
#include <stdio.h>
#include <stdlib.h>
#define PARENT(i) (i) / 2 // parent of i
#define LEFT(i) (i) << 1 // left child
#define RIGHT(i) ((i) << 1) + 1 // right child
#define swap(a, b, t) { (t) = (a); (a) = (b); (b) = (t); }
#define N 5
#define MAXVAL 50
#define MAXNUM MAXVAL
typedef struct _node {
int data;
struct _node *next;
}Node;
typedef Node *List;
typedef Node HeapType;
static List head[N]; // N list to be combined
static int heap_size = 0;
static HeapType heap[N+1];
static int ans[MAXNUM+1]; // finaly sorted array
void list_init(List *L)
{
*L = (List)malloc(sizeof(Node));
if (*L == NULL)
exit(-1);
(*L)->next = NULL;
}
Node *make_node(Node *a, int val)
{
a = (List)malloc(sizeof(Node));
if (a == NULL)
return NULL;
a->data = val;
a->next = NULL;
return a;
}
/* create n lists, each list in an ascending order */
void creat_lists(List head[], int n)
{
int i, val, listno;
Node *tn;
for (i = 0; i < n; i++) {
list_init(&head[i]);
}
srand(time(NULL));
for (val = MAXVAL; val > 0; val--) {
listno = rand() % N; // random list number
if ( (tn = make_node(tn, val)) == NULL) {
fprintf(stderr, "make node failed\n");
return ;
}
tn->data = val;
tn->next = head[listno]->next;
head[listno]->next = tn;
}
}
void print_list(List head)
{
List p = head->next;
for ( ; p != NULL; p = p->next)
printf("%3d ", p->data);
printf("\n");
}
/*
* LEFT(i) and RIGHT(i) are alread min-leap
* the heap[i] may greater than either the left or right child
* so adjust the heap when necessary.
*/
void min_heapify(HeapType *heap, int i)
{
int l, r, smallest;
HeapType tmp;
l = LEFT(i);
r = RIGHT(i);
if (l <= heap_size && heap[l].data < heap[i].data)
smallest = l;
else
smallest = i;
if (r <= heap_size && heap[r].data < heap[smallest].data)
smallest = r;
if (smallest != i) {
swap(heap[i], heap[smallest], tmp);
min_heapify(heap, smallest);
}
}
/* insert a node to the min-heap */
void min_heap_insert(HeapType *heap, int i, Node node)
{
while (i > 1 && heap[PARENT(i)].data > node.data) {
heap[i] = heap[PARENT(i)];
i = PARENT(i);
}
heap[i] = node;
heap_size++;
}
/* remove the minmum element of the heap */
void heap_extract_min(HeapType *heap)
{
int i;
heap[1] = heap[heap_size];
heap_size--;
min_heapify(heap, 1);
}
/* sort k lists using a min-heap, runtime: O(n*lgk) */
void heapsort_kcombine(HeapType *heap, const List head[], int k)
{
int i, listno;
for (i = 0; i < k; i++) {
min_heap_insert(heap, i+1, *head[i]->next);
}
i = 0;
while (heap_size > 0) {
ans[i++] = heap[1].data;
if (heap[1].next != NULL) { // 链表不为空
heap[1] = *heap[1].next;
min_heapify(heap, 1);
} else {
heap_extract_min(heap);
}
}
}
void print_heap(HeapType *heap)
{
int i;
for (i = 1; i <= heap_size; i++) {
printf("%3d\n", heap[i].data);
}
}
int main()
{
int i;
printf("Create %d lists as follow:\n", N);
creat_lists(head, N);
for (i = 0; i < N; i++) {
printf("list %d: ", i+1);
print_list(head[i]);
}
heapsort_kcombine(heap, head, N);
printf("%d list sorted:\n", N);
for (i = 0; i < MAXNUM; i++)
printf("%3d%s", ans[i], (i+1) % 10 == 0 ? "\n" : " ");
exit(0);
}