3o_3v

heap c style

Sep 9th, 2022 (edited)
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.87 KB | None | 0 0
  1. #include <cstdio>
  2. #include <malloc.h>
  3.  
  4. struct heap {
  5.     int size;
  6.     int ind;
  7.     int *mas;
  8. };
  9.  
  10. heap *nheap(int size) {
  11.     heap *h = (heap *) malloc(sizeof(heap));
  12.     h->ind = 0;
  13.     h->size = size;
  14.     h->mas = (int *) (malloc(size*sizeof(int)));
  15.     return h;
  16. }
  17.  
  18. void sifting(heap *h, int ind) {
  19.     int *mas = h->mas;
  20.     if (ind == 0) {
  21.         return;
  22.     }
  23.     if (ind & 1) {
  24.         if (mas[ind] > mas[(ind - 1)/2]) {
  25.             int t = mas[ind];
  26.             mas[ind] = mas[(ind - 1)/2];
  27.             mas[(ind - 1)/2] = t;
  28.         }
  29.         sifting(h, (ind - 1)/2);
  30.     } else {
  31.         if (mas[ind] > mas[ind/2 - 1]) {
  32.             int t = mas[ind];
  33.             mas[ind] = mas[ind/2 - 1];
  34.             mas[ind/2 - 1] = t;
  35.         }
  36.         sifting(h, ind/2 - 1);
  37.     }
  38. }
  39.  
  40. void add_el_to_heap(heap *h, int element) {
  41.     if (h->ind >= h->size) {
  42.         h->size *= 2;
  43.         int *nmas = (int *) realloc(h->mas, h->size*sizeof(int));
  44.         if (nmas) {
  45.             h->mas = nmas;
  46.         }
  47.     }
  48.     h->mas[h->ind] = element;
  49.     sifting(h, h->ind++);
  50. }
  51.  
  52. void heapify(heap *h, int ind) {
  53.     if (ind >= h->ind/2) {
  54.         return;
  55.     }
  56.     int *mas = h->mas;
  57.     int el = mas[ind];
  58.     if (2*ind + 2 == h->ind) {
  59.         if (el < mas[2*ind + 2]) {
  60.             mas[ind] = mas[2*ind + 2];
  61.             mas[2*ind + 2] = el;
  62.         }
  63.     } else {
  64.         int maxind = (mas[2*ind + 1] > mas[2*ind + 2]) ? (2*ind + 1) : (2*ind + 2);
  65.         mas[ind] = mas[maxind];
  66.         mas[maxind] = el;
  67.     }
  68. }
  69.  
  70. int delmax(heap *h){
  71.     if(h->ind == 0){
  72.         return 0;
  73.     }
  74.     int *mas = h->mas;
  75.     int max = mas[0];
  76.     mas[0] = mas[--h->ind];
  77.     heapify(h, 0);
  78.     return max;
  79. }
  80.  
  81. void printheap(heap *h) {
  82.     for (int i = 0; i < h->ind; i++) {
  83.         printf("%d ", h->mas[i]);
  84.     }
  85.     printf("\n");
  86. }
  87.  
  88. int main() {
  89.     heap *h = nheap(8);
  90.     add_el_to_heap(h, 5);
  91.     add_el_to_heap(h, 4);
  92.     add_el_to_heap(h, 8);
  93.     add_el_to_heap(h, 3);
  94.     add_el_to_heap(h, 1);
  95.     add_el_to_heap(h, 0);
  96.     add_el_to_heap(h, 16);
  97.     add_el_to_heap(h, 4);
  98.     add_el_to_heap(h, 12);
  99.     for(int i = 0; i < 9; i++){
  100.         printf("%d ", delmax(h));
  101.     }
  102. }
  103.  
  104.  
Advertisement
Add Comment
Please, Sign In to add comment