v 0. Pasted by slipstak2 as cpp at 2011-11-08 16:01:31 MSK and set expiration to never.

Paste will expire never.

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int SIZE = 31;
  6.  
  7. struct Node {
  8.     int data;
  9.     Node* left;
  10.     Node* right;
  11.     Node(){}
  12.     Node(int Data) {
  13.         data = Data;
  14.         left = 0;
  15.         right = 0;
  16.     }
  17.     Node(const Node &n) {
  18.         data = n.data;
  19.         Node *l = 0, *r = 0;
  20.         if (n.left) l = new Node(*n.left);
  21.         if (n.right) r = new Node(*n.right);
  22.         left = l;
  23.         right = r;     
  24.     }
  25.     ~Node() {
  26.         if (left) {
  27.             delete left;
  28.             left = 0;
  29.         }
  30.         if (right) {
  31.             delete right;
  32.             right = 0;
  33.         }
  34.     }
  35.  
  36. };
  37.  
  38. struct binomial_queue {
  39.     Node* mas[SIZE];
  40.     int size;
  41.     binomial_queue(){memset(mas,0,sizeof(mas)); size = 0;}
  42.     binomial_queue(const binomial_queue &bq) {
  43.  
  44.         memset(mas,0,sizeof(mas));
  45.  
  46.         size = bq.size;
  47.         for (int i=0;i<SIZE;i++) {
  48.             if (bq.mas[i]) {
  49.                 Node* deepCopy = new Node(*bq.mas[i]);
  50.                 mas[i] = deepCopy;
  51.             }
  52.         }
  53.     }
  54.     ~binomial_queue() {
  55.         for (int i=0;i<SIZE;++i) {
  56.             if (mas[i])
  57.                 delete mas[i];
  58.         }
  59.     }
  60.     void clear() {
  61.         memset(mas,0,sizeof(mas)); size = 0;
  62.     }
  63.     void read() {
  64.         int n,val;
  65.         scanf("%d",&n);
  66.         for (int i=0;i<n;i++) {
  67.             scanf("%d", &val);
  68.             add(val);
  69.         }
  70.     }
  71.     void output(char * str) {
  72.         printf("%s : ", str);
  73.         binomial_queue bq = *this;
  74.         while (!bq.empty())
  75.             printf("%d ", bq.getMax());
  76.         printf("\n");
  77.     }
  78.     bool empty() {
  79.         return size == 0;
  80.     }
  81.     Node* join(Node* f, Node *s) {
  82.         if (f->data > s->data) {
  83.             s->right = f->left; f->left = s; return f;
  84.         }
  85.         else {
  86.             f->right = s->left; s->left = f; return s;
  87.         }
  88.     }
  89.     int num(int c, int b, int a) {
  90.         return 4*c + 2*b + a;
  91.     }
  92.     void joinBQ(Node* a[], Node* b[]) {
  93.         Node* c = 0;
  94.         for (int i=0;i<SIZE;i++) {
  95.             switch(num(c!=0,b[i]!=0,a[i]!=0)) {
  96.                 case 2: a[i] = b[i]; break;
  97.                 case 3: c = join(a[i],b[i]); a[i] = 0; break;
  98.                 case 4: a[i] = c; c = 0; break;
  99.                 case 5: c = join(a[i],c); a[i] = 0; break;
  100.                 case 6:
  101.                 case 7: c = join(b[i],c); break;
  102.             }
  103.         }
  104.     }
  105.     void joinBQ(binomial_queue &bq) {
  106.         joinBQ(mas, bq.mas);
  107.         size += bq.size;
  108.         bq.clear();
  109.     }
  110.     void add(int val) {
  111.         Node* newNode = new Node(val);
  112.         Node* curNode = newNode;
  113.         for (int i=0;i<SIZE;i++) {
  114.             if (mas[i] == NULL) {
  115.                 mas[i] = curNode;
  116.                 break;
  117.             }
  118.             else {
  119.                 curNode = join(curNode,mas[i]);
  120.                 mas[i] = NULL;
  121.             }
  122.         }
  123.         size++;
  124.     }
  125.     int getMax() {
  126.         int res = 0;
  127.         int resPos = -1;
  128.         for (int i=0;i<SIZE;i++) {
  129.             if (mas[i] && mas[i]->data > res) {
  130.                 res = mas[i]->data;
  131.                 resPos = i;
  132.             }
  133.         }
  134.         Node** tmp = new Node*[SIZE];
  135.         memset(tmp,0,sizeof(tmp)*SIZE);
  136.         Node* cur = mas[resPos]->left;
  137.         for (int i=resPos-1;i>=0;i--) {
  138.             tmp[i] = new Node(*cur);
  139.             cur = cur->right;
  140.             tmp[i]->right = 0;
  141.         }
  142.         delete mas[resPos];
  143.         mas[resPos] = 0;
  144.  
  145.         joinBQ(mas, tmp);
  146.         delete tmp;
  147.         size--;
  148.         return res;
  149.     }
  150. };
  151.  
  152. int main() {
  153.     freopen("input.txt","r",stdin);
  154.     freopen("output.txt","w",stdout);
  155.  
  156.     binomial_queue bq1,bq2;
  157.     bq1.read(); bq2.read();
  158.  
  159.     bq1.output("first  bin_queue");
  160.     bq2.output("second bin_queue");
  161.  
  162.     bq1.joinBQ(bq2);
  163.  
  164.     bq1.output("union first&second bin_queue");
  165.  
  166.     return 0;
  167. }


Editing is locked.