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. {
  18.     Node* head = list;
  19.     while (head != NULL)
  20.     {
  21.         cout << head->data << " ";
  22.         head = head->next;
  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[0]->next == NULL)
  130.     {
  131.         pop = heap[0];
  132.         (*heap_size)--;
  133.         heap[0] = heap[*heap_size];
  134.         Heapify(heap, *heap_size, 0);
  135.     }
  136.     else
  137.     {
  138.         pop = heap[0];
  139.         heap[0] = heap[0]->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[0], heap[1], 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. OK, I Understand
 
Top