• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Nov 9th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include "Profiler.h"
3. #define AVG_K_5 ("Average_Case_K_5");
4. #define AVG_K_10 ("Average_Case_K_10");
5. #define AVG_K_100 ("Average_Case_K_100");
6. using namespace std;
7. Profiler profiler("Merge K Sorted Lists");
8.
9. int OP;
10.
11. struct Node {
12.     int data;
13.     struct Node* next;
14. };
15.
16. void PrintList(Node* list)
17. {
20.     {
21.         cout << head->data << " ";
23.     }
24.     cout << endl;
25. }
26.
27. Node* createNode(int data)
28. {
29.     Node* newNode = (Node*)malloc(sizeof(Node));
30.     if (newNode)
31.     {
32.         newNode->data = data;
33.         newNode->next = NULL;
34.     }
35.     return newNode;
36. }
37.
38. void InsertNode(Node** list, int data)
39. {
40.     Node* node = createNode(data/*, KeyList*/);
41.     if (list == NULL)
42.         *list = node;
43.     else
44.     {
45.         node->next = *list;
46.         *list = node;
47.     }
48. }
49.
50. void createList(Node** list, int size)
51. {
52.     int* a = (int*)malloc(size * sizeof(int));
53.     FillRandomArray(a, size, 10, 50000, false, 1);
54.     for (int i = size-1; i >= 0; i--)
55.         InsertNode(list, a[i]);
56.
57. }
58.
59. Node** createKLists(int n, int k)
60. {
61.     int length;
62.     Node** arrayLists = (Node**)malloc(k * sizeof(Node*));
63.     if (n % k == 0)
64.     {
65.         for (int i = 0; i < k; i++)
66.         {
67.             length = n / k;
68.             arrayLists[i] = (Node*)malloc(length * sizeof(Node));
69.             arrayLists[i] = NULL;
70.             createList(&arrayLists[i], length);
71.         }
72.     }
73.     else
74.     {
75.         for (int i = 0; i < k; i++)
76.         {
77.             if (i < n % k)
78.                 length = (n / k) + 1;
79.             else
80.                 length = n / k;
81.             arrayLists[i] = (Node*)malloc(length * sizeof(Node));
82.             arrayLists[i] = NULL;
83.             createList(&arrayLists[i], length);
84.         }
85.     }
86.
87.     return arrayLists;
88. }
89.
90. void Heapify(Node** heap, int n, int i)
91. {
92.
93.     int root;
94.     int left = 2 * i + 1; //the left child of the node i is at (2*i+1) index
95.     int right = 2 * i + 2; //the right child of the node i is at (2*i+2) index
96.
97.     if (left<n && heap[left]>heap[i]) //we check whether or not the left child is larger than the root and if it is, the root will take the index value of the left child
98.     {
99.         root = left;
100.         OP++;
101.     }
102.     else root = i;
103.     if (left < n) OP++;
104.
105.     if (right<n && heap[right]>heap[root]) //we check whether or not the right child is larger than the root and if it is, the root will take the index value of the right child
106.     {
107.         root = right;
108.         OP++;
109.     }
110.     if (right < n) OP++;
111.
112.     if (root != i)
113.     {
114.         swap(heap[i], heap[root]);
115.         OP += 3;
116.         Heapify(heap, n, root); //if the root doesn't have the same value as the initial value, then we swap the terms and recursively heapify the affected subtree
117.     }
118. }
119.
120. void MinHeap(Node** heap, int n)
121. {
122.     for (int i = n / 2 - 1; i >= 0; i--)
123.         Heapify(heap, n, i);
124. }
125.
126. Node* popHeap(Node** heap, int* heap_size)
127. {
128.     Node* pop = NULL;
129.     if (heap->next == NULL)
130.     {
131.         pop = heap;
132.         (*heap_size)--;
133.         heap = heap[*heap_size];
134.         Heapify(heap, *heap_size, 0);
135.     }
136.     else
137.     {
138.         pop = heap;
139.         heap = heap->next;
140.         Heapify(heap, *heap_size, 0);
141.     }
142.     return pop;
143. }
144.
145. void Merge2Lists(Node* list1, Node* list2, Node* result)
146. {
147.     Node* current = NULL;
148.     while (list1 != NULL && list2 != NULL)
149.     {
150.         if (list1->data < list2->data)
151.         {
152.             current = list1;
153.             list1 = list1->next;
154.             current->next = NULL;
155.             result->next = current;
156.         }
157.         else
158.         {
159.             current = list2;
160.             list2 = list2->next;
161.             current->next = NULL;
162.             result->next = current;
163.         }
164.         result = result->next;
165.     }
166.
167.     if (list1 == NULL)
168.         result->next = list2;
169.     else
170.         result->next = list1;
171. }
172.
173. Node* MergeKLists(Node** arrayLists, int n, int k)
174. {
175.     Node* final = NULL;
176.     Node* result = NULL;
177.     Node** heap = (Node**)malloc(k * sizeof(Node*));
178.     int heap_size = k;
179.     for (int i = 0; i < k; i++)
180.         heap[i] = arrayLists[i]; //we memorize in heap the heads of each list
181.     MinHeap(heap, heap_size); //we heapify the constructed heap
182.
183.     result = popHeap(heap, &heap_size);
184.     final = result;
185.
186.     while (heap_size > 2)
187.     {
188.         Node* pop = popHeap(heap, &heap_size);
189.         final->next = pop;
190.         final = final->next;
191.     }
192.     Merge2Lists(heap, heap, final);
193.
194.     return result;
195. }
196.
197. void demo()
198. {
199.     int n = 20, k = 4;
200.     Node** arrayLists = createKLists(n, k);
201.     Node* result = NULL;
202.     cout << "The " << k << " lists are:\n";
203.     for (int i = 0; i < k; i++)
204.         PrintList(arrayLists[i]);
205.     result= MergeKLists(arrayLists, n, k);
206.     cout << "\nThe merged list:\n";
207.     PrintList(result);
208.
209.
210. }
211.
212. int main()
213. {
214.
215.     demo();
216.     return 0;
217. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top