Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Nov 14th, 2017 56 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  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
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