Platinum2d

Binary Heap - Modular code

Jun 6th, 2017
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.58 KB | None | 0 0
  1. //basic.h
  2.  
  3. #ifndef BASIC_H
  4. #define BASIC_H
  5.  
  6. #define _CRT_SECURE_NO_WARNINGS
  7. #include <stdlib.h>
  8. #include <stdio.h>
  9. #include <stdbool.h>
  10. #include <string.h>
  11. #include <stdint.h>
  12.  
  13. typedef int element;
  14.  
  15. extern element *toDynamic(const element v[], uint32_t n);
  16. extern bool isLeaf(uint32_t i, uint32_t heap_size);
  17. extern void swap(element *v, uint32_t a, uint32_t b);
  18. extern uint32_t left(uint32_t i);
  19. extern uint32_t right(uint32_t i);
  20. extern uint32_t parent(uint32_t i);
  21. extern element Max(element a, element b);
  22. extern void moveDown(element *v, uint32_t i, uint32_t heap_size);
  23. extern void moveUp(element *v, uint32_t i);
  24. extern void build_heap(element *v, uint32_t heap_size);
  25. extern void deleteNode(element *v, uint32_t i, uint32_t *heap_size);
  26. extern element *insertNode(element *v, element e, uint32_t *heap_size);
  27. extern bool isGreater(element lhs, element rhs);
  28. extern bool isLess(element lhs, element rhs);
  29. extern bool isEqual(element lhs, element rhs);
  30. extern void showHeap(element *v, uint32_t heap_size);
  31. extern bool isInvalidNode(uint32_t i, uint32_t heap_size);
  32. extern void printElement(element e);
  33.  
  34. #endif /*!BASIC_H*/
  35.  
  36. //basic.c
  37.  
  38. element *toDynamic(const element v[], uint32_t n)
  39. {
  40.     element *ret = (element*) malloc(n * sizeof(element));
  41.     memcpy(ret, v, n * sizeof(element));
  42.     return ret;
  43. }
  44.  
  45. element *copyHeap(element *v, uint32_t heap_size)
  46. {
  47.     element *copied = (element*)malloc((heap_size + 1) * sizeof(element));
  48.  
  49.     memcpy(copied, v, (heap_size + 1) * sizeof(element));
  50.     return copied;
  51. }
  52.  
  53. bool isLeaf(uint32_t i, uint32_t heap_size)
  54. {
  55.     return i > parent(heap_size);
  56. }
  57.  
  58. void swap(element *v, uint32_t a, uint32_t b)
  59. {
  60.     element *temp = (element*) malloc(sizeof(element));
  61.     memcpy(temp, &v[a], sizeof(element));
  62.     memcpy(&v[a], &v[b], sizeof(element));
  63.     memcpy(&v[b], temp, sizeof(element));
  64. }
  65.  
  66. uint32_t left(uint32_t i)
  67. {
  68.     return 2 * i;
  69. }
  70.  
  71. uint32_t right(uint32_t i)
  72. {
  73.     return 2 * i + 1;
  74. }
  75.  
  76. uint32_t parent(uint32_t i)
  77. {
  78.     return (i != 1 && i != 0) ? i / 2 : 0;
  79. }
  80.  
  81. bool isGreater(element lhs, element rhs)
  82. {
  83.     return lhs > rhs;
  84. }
  85.  
  86. bool isEqual(element lhs, element rhs)
  87. {
  88.     return lhs == rhs;
  89. }
  90.  
  91. bool isLess(element lhs, element rhs)
  92. {
  93.     return !isEqual(lhs, rhs) && !isGreater(lhs, rhs);
  94. }
  95.  
  96. element Max(element a, element b)
  97. {
  98.     if (isGreater(a, b)) return a;
  99.     else if (isLess(a, b)) return b;
  100.  
  101.     return a;
  102. }
  103.  
  104. void moveDown(element *v, uint32_t i, uint32_t heap_size)
  105. {
  106.     if (isLeaf(i, heap_size)) return;
  107.  
  108.     uint32_t l = left(i), r = right(i);
  109.  
  110.     uint32_t u = l > r ? l : r;
  111.     if (isLess(v[i], v[u]))
  112.     {
  113.         swap(v, i, u);
  114.         moveDown(v, u, heap_size);
  115.     }
  116. }
  117.  
  118. void moveUp(element *v, uint32_t i)
  119. {
  120.     while (i != 1 && (isGreater(v[i], v[parent(i)]) || isEqual(v[i], v[parent(i)])))
  121.     {
  122.         uint32_t father = parent(i);
  123.  
  124.         swap(v, i, father);
  125.         i = father;
  126.     }
  127. }
  128.  
  129. void heapify(element *v, uint32_t i, uint32_t heap_size)
  130. {
  131.     uint32_t l, r, largest = i;
  132.     l = left(i);
  133.     r = right(i);
  134.  
  135.     if ((l <= heap_size) && isGreater(v[l], v[r]))
  136.         largest = l;
  137.  
  138.     if ((r <= heap_size) && isGreater(v[r], v[largest]))
  139.         largest = r;
  140.  
  141.     if (largest != i)
  142.     {
  143.         swap(v, i, largest);
  144.         heapify(v, largest, heap_size);
  145.     }
  146.  
  147.     return;
  148. }
  149.  
  150. void build_heap(element *v, uint32_t heap_size)
  151. {
  152.     int i;
  153.     for (i = heap_size / 2; i >= 1; i--)
  154.         heapify(v, i, heap_size);
  155. }
  156.  
  157. void deleteNode(element *v, uint32_t i, uint32_t *heap_size)
  158. {
  159.     swap(v, 1, *heap_size);
  160.     (*heap_size)--;
  161.     heapify(v, 1, *heap_size);
  162. }
  163.  
  164. void heapsort(element *v, uint32_t dim)
  165. {
  166.     int i, heap_size = dim;
  167.     for (i = dim; i >= 2; i--)
  168.     {
  169.         swap(v, 1, i);
  170.         heapify(v, 1, --heap_size);
  171.     }
  172. }
  173.  
  174. element *insertNode(element *v, element e, uint32_t *heap_size)
  175. {
  176.     (*heap_size)++;
  177.     v = (element*) realloc(v, (*heap_size + 1) * sizeof(element));
  178.     v[*heap_size] = e;
  179.     moveUp(v, *heap_size);
  180.  
  181.     return v;
  182. }
  183.  
  184. void printElement(element e)
  185. {
  186.     printf("%d ", e);
  187. }
  188.  
  189. bool isInvalidNode(uint32_t i, uint32_t heap_size)
  190. {
  191.     return i > heap_size;
  192. }
  193.  
  194. void quicksort(element *v, int first, int last)
  195. {
  196.     if (first < last)
  197.     {
  198.         int i = first, j = last;
  199.         element pivot = v[(first + last) / 2];
  200.  
  201.         do
  202.         {
  203.             while (isGreater(v[i], pivot)) i++;
  204.             while (isLess(v[j], pivot)) j--;
  205.             if (i <= j)
  206.             {
  207.                 swap(v, i, j);
  208.                 i++, j--;
  209.             }
  210.         } while (i <= j);
  211.  
  212.         quicksort(v, first, j);
  213.         quicksort(v, i, last);
  214.     }
  215. }
  216.  
  217. void showHeap(element *v, uint32_t heap_size)
  218. {
  219.     element *copied = copyHeap(v, heap_size);
  220.     quicksort(copied, 1, heap_size);
  221.     for (uint32_t i = 1; i <= heap_size; i++) printElement(copied[i]);
  222.     free(copied);
  223. }
  224.  
  225. int main(void)
  226. {
  227.     return EXIT_SUCCESS;
  228. }
Advertisement
Add Comment
Please, Sign In to add comment