SHARE
TWEET

Untitled

a guest Nov 14th, 2017 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // HR.C
  2. // This code is provided to students in ELEC278 for use in Lab 5.
  3. // History:
  4. // 161101   HR  First release
  5. // 171102   DA  Minor edits
  6.  
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9.  
  10. // Heap data structure.  Heap contains pointer to an array of size
  11. // maxSize.  See initHeap() for details on heap instance creation.
  12. typedef struct Heap {
  13.     int *a;         // pointer to array containing heap elements
  14.     int last;       // index of last used location in array
  15.     int maxSize;    // size of array (note maxSize = maxIndex + 1)
  16. } Heap;
  17.  
  18.  
  19. // Useful shorthand.
  20. // Left child of node i is at (2*i) +1, right child is at (2*i)+2
  21. #define LeftChild(i)    ((2 * i) + 1)
  22. #define RiteChild(i)    ((2 * i) + 2)
  23. #define Parent(i)       ((i-1)/2)
  24. #define NOTREE          (-1)
  25.  
  26.  
  27. Heap* initHeap(int size)
  28. // Create an instance of a heap. Parameter size is size of array to
  29. // allocate.  Returns pointer to newly created heap storage if memory
  30. // was obtained; NULL if there was any failure to obtain memory.
  31. {
  32.     Heap    *h = malloc(sizeof(Heap));
  33.     if (h != NULL)  {
  34.         h->a = malloc(sizeof(int) * size);
  35.         if (h->a == NULL)   {
  36.             // Didn't get memory for the array - give up completely
  37.             free (h);
  38.             h = NULL;
  39.         } else  {
  40.             h->last = NOTREE;   // so far, nothing in heap
  41.             h->maxSize = size;  // so we know how many can be stored
  42.             }
  43.         }
  44.     return h;      
  45. }//initHeap()
  46.  
  47.  
  48. void swap(int* heap, int i, int j)
  49. // Swap elements at locations i and j in heap.
  50. {
  51.     int t = heap[i];        // save element i in temporary location
  52.     heap[i] = heap[j];      // copy element j into location i
  53.     heap[j] = t;            // copy saved element i into location j
  54. }//swap()
  55.  
  56.  
  57. void reheapUp(Heap* heap, int index)
  58. {
  59.     if (index <= 0)
  60.         return;
  61.     else    {
  62.         int parent_index = Parent(index);
  63.         if (heap->a[index] < heap->a[parent_index])
  64.             swap(heap->a, index, parent_index);
  65.         else
  66.             return;
  67.         reheapUp(heap, parent_index);
  68.         }
  69. }//reheapUp()
  70.  
  71.  
  72. void reheapDown(Heap* heap, int i)
  73. {
  74.     int left, right, smallest, smallestIndex;
  75.  
  76.     if (LeftChild(i) <= heap->last) {
  77.         left = heap->a[LeftChild(i)];
  78.         if (RiteChild(i) <= heap->last) {
  79.             right = heap->a[RiteChild(i)];
  80.         } else {
  81.             right = NOTREE;
  82.             }
  83.         if (left < right || right == NOTREE) {
  84.             smallest = left;
  85.             smallestIndex = LeftChild(i);
  86.         } else {
  87.             smallest = right;
  88.             smallestIndex = RiteChild(i);
  89.             }
  90.         if (heap->a[i] > smallest) {
  91.             swap(heap->a, i, smallestIndex);
  92.             reheapDown(heap, smallestIndex);
  93.             }
  94.         }
  95. }//reheapDown()
  96.  
  97.  
  98. int withdrawMin(Heap* h)
  99. // Smallest value in heap is at the top of the tree - index 0 in the array
  100. // used to store the tree.  Save that value, then fix the heap.
  101. {
  102.     int min = h->a[0];          // save smallest value
  103.     h->a[0] = h->a[h->last];    // move last element in array to top
  104.     h->last--;                  // indicate heap is one smaller
  105.     reheapDown(h,0);            // turn tree into heap by moving top
  106.                                 // element down to correct position
  107.     return min;                 // return smallest value in heap
  108. }
  109.  
  110.  
  111. void insert(Heap* h, int x)
  112. // Add new value x to heap
  113. {
  114.     // Is there room?
  115.     if (h->last == h->maxSize - 1)  return;
  116.     h->a[++h->last] = x;
  117.     reheapUp(h, h->last);
  118. }//insert()
  119.  
  120.  
  121. int findMin(Heap* h)
  122. // Tell caller smallest value in heap but do not remove value from heap
  123. {
  124.     return ((h != NULL) && (h->last != NOTREE)) ? h->a[0] : NOTREE;
  125. }//findMin()
  126.  
  127.  
  128. void print(Heap* heap)
  129. // Print array holding the heap.  Does not make levels obvious.
  130. {
  131.     int i;
  132.     printf("Heap: ");
  133.     for (i = 0; i <= heap->last; i++) {
  134.         printf("%d, ", heap->a[i]);
  135.         }
  136.     printf("\n");
  137. }//print()
  138.  
  139.  
  140. Heap* copyHeap(Heap* h ){
  141.     Heap* newH = initHeap(h->maxSize);
  142.     int i;
  143.     for(i=0;i<=h->last;i++){
  144.         newH->a[i] = h->a[i];
  145.     }
  146.     newH->last = h->last;
  147.     return newH;
  148. }
  149.  
  150.  
  151. int findkth(Heap* h, int k)
  152. // Finds the kth smalled item n heap, by removing k items, if possible.
  153. {
  154.     Heap* newH = copyHeap(h);
  155.     int min = NOTREE;
  156.     while(k--){
  157.         min = withdrawMin(newH);
  158.     }
  159.     return min;
  160. }
  161.  
  162.  
  163. Heap* heapify(int a[], int size)
  164. {
  165.     int     i;
  166.     Heap* h = malloc(sizeof(Heap));
  167.     h->last = 0;
  168.     h->maxSize = size;
  169.     h->a = a;
  170.  
  171.     for(i=0;i<size;i++){
  172.         reheapUp(h,h->last);
  173.         //print(h);
  174.         h->last++;
  175.     }
  176.     h->last--;
  177.     return h;
  178. }
  179.  
  180.  
  181. // Two versions of main() - the first performs a static test; the second
  182. // is for production.
  183.  
  184. //#define TESTING
  185.  
  186. #ifdef TESTING
  187. int main() {
  188.     int a[] = { 23, 7, 92, 6, 12, 14, 40, 44, 20, 21 };
  189.     Heap* h = heapify(a, 10);
  190.     int  temp1, temp2;
  191.     print(h);
  192.     temp1 = withdrawMin(h);
  193.     print(h);
  194.     temp2 = withdrawMin(h);
  195.     print(h);
  196.     insert (h, temp1+temp2);
  197.     print (h);
  198.     withdrawMin(h);
  199.     print(h);
  200.     /*
  201.     Alternate test code
  202.      Heap* h = initHeap(32);
  203.      insert(h, 10);
  204.      print(h);
  205.      insert(h, 2);
  206.      print(h);
  207.      insert(h, 4);
  208.      print(h);
  209.      insert(h, 1);
  210.      print(h);
  211.      insert(h, 5);
  212.      print(h);
  213.      insert(h, 3);
  214.      print(h);
  215.      while(h->last!=NOTREE){
  216.      printf("%d is withdrawn\n",withdrawMin(h));
  217.      print(h);
  218.      }
  219.      */
  220. }
  221.  
  222. #else
  223.  
  224.  
  225. int main()
  226. {
  227.     int     i, k, n, ctr = 0, tmp1, tmp2;
  228.     int     *a;
  229.     Heap    *h;
  230.  
  231.     // First input gives you two parameters
  232.     scanf("%d %d",&n,&k);
  233.     a = malloc(sizeof(int)*n);
  234.     // Second collection of input gives you all the data
  235.     for(i=0;i<n;i++)
  236.         scanf("%d",&a[i]);
  237.    
  238.     // *** Your code goes here ***
  239.     // You need to make the array of data into a heap, then you need
  240.     // to apply Jesse's algorithm on the data.
  241.     // ---<SNIP>---
  242.     h = initHeap(n);
  243.     for (i = 0; i < n; i++) {
  244.         insert(h, a[i]);
  245.     }
  246.     while (findMin(h) < k) {
  247.         if (h->last == 0) {
  248.             ctr = -1;
  249.             break;
  250.         }
  251.         ctr++;
  252.         tmp1 = withdrawMin(h);
  253.         tmp2 = withdrawMin(h);
  254.         //printf("%d, %d -> %d\n", tmp1, tmp2, tmp1 + 2 * tmp2);
  255.         insert(h, tmp1 + 2 * tmp2);
  256.     }
  257.     // ---<SNIP>---
  258.     printf("%d\n",ctr);
  259.     return 0;
  260. }
  261.  
  262. #endif
RAW Paste Data
Top