peltorator

Leftist-Heap

Apr 12th, 2019
138
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. struct Node // min-heap on int64
  3. {
  4.     Node *left;
  5.     Node *right;
  6.     ll x;
  7.     int d;
  8.  
  9.     Node(ll x):
  10.         left(NULL),
  11.         right(NULL),
  12.         x(x),
  13.         d(1) {}
  14. };
  15.  
  16. int d(Node *v)
  17. {
  18.     if (v == NULL)
  19.         return 0;
  20.     else
  21.         return v->d;
  22. }
  23.  
  24. Node* merge(Node *a, Node *b)
  25. {
  26.     if (a == NULL)
  27.         return b;
  28.     if (b == NULL)
  29.         return a;
  30.     if (a->x > b->x)
  31.         swap(a, b);
  32.     a->right = merge(a->right, b);
  33.     if (d(a->right) > d(a->left))
  34.         swap(a->right, a->left);
  35.     a->d = d(a->right) + 1;
  36.     return a;
  37. }
  38.  
  39. Node* push(Node *root, ll x)
  40. {
  41.     return merge(root, new Node(x));
  42. }
  43.  
  44. Node* pop(Node *root)
  45. {
  46.     return merge(root->left, root->right);
  47. }
  48.  
  49. ll min(Node *root)
  50. {
  51.     return root->x;
  52. }
RAW Paste Data