Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct heap {
- int a[100001];
- int heap_size;
- heap() {
- heap_size = 0;
- }
- void sift_up(int i) {
- if (a[i / 2] > a[i]) {
- swap(a[i / 2], a[i]);
- sift_up(i / 2);
- }
- }
- void sift_down(int i) {
- while (2 * i < heap_size) {
- int l = 2 * i;
- int r = 2 * i + 1;
- int j = l;
- if (r <= heap_size && a[r] < a[l]) {
- j = r;
- }
- if (a[i] <= a[j]) {
- break;
- }
- swap(a[i], a[j]);
- i = j;
- }
- }
- void put(int n) {
- heap_size++;
- a[heap_size] = n;
- sift_up(heap_size);
- }
- int get() {
- int ans = a[1];
- a[1] = a[heap_size];
- heap_size--;
- sift_down(1);
- return ans;
- }
- void heapify() {
- for (int i = heap_size / 2; i > 0; i--) {
- sift_down(i);
- }
- }
- };
- обращение к функциям определенной структуры:
- heap a;
- a.heap_size = 100
- for (int i = 0; i < 100; i++) {
- cin << a.a[i];
- }
- a.heapify();
- a.get();
- a.put(n);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement