Advertisement
NHumme

Heap - struct

Dec 16th, 2018
241
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.92 KB | None | 0 0
  1. struct heap {
  2.     int a[100001];
  3.     int heap_size;
  4.    
  5.     heap() {
  6.         heap_size = 0;
  7.     }
  8.  
  9.     void sift_up(int i) {
  10.         if (a[i / 2] > a[i]) {
  11.             swap(a[i / 2], a[i]);
  12.             sift_up(i / 2);
  13.         }
  14.     }
  15.  
  16.     void sift_down(int i) {
  17.         while (2 * i < heap_size) {
  18.             int l = 2 * i;
  19.             int r = 2 * i + 1;
  20.             int j = l;
  21.             if (r <= heap_size && a[r] < a[l]) {
  22.                 j = r;
  23.             }
  24.             if (a[i] <= a[j]) {
  25.                 break;
  26.             }
  27.             swap(a[i], a[j]);
  28.             i = j;
  29.         }
  30.     }
  31.  
  32.     void put(int n) {
  33.         heap_size++;
  34.         a[heap_size] = n;
  35.         sift_up(heap_size);
  36.     }
  37.  
  38.     int get() {
  39.         int ans = a[1];
  40.         a[1] = a[heap_size];
  41.         heap_size--;
  42.         sift_down(1);
  43.         return ans;
  44.     }
  45.  
  46.     void heapify() {
  47.         for (int i = heap_size / 2; i > 0; i--) {
  48.             sift_down(i);
  49.         }
  50.     }
  51. };
  52.  
  53. обращение к функциям определенной структуры:
  54. heap a;
  55. a.heap_size = 100
  56. for (int i = 0; i < 100; i++) {
  57.     cin << a.a[i];
  58. }
  59. a.heapify();
  60. a.get();
  61. a.put(n);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement