peltorator

Skew-Heap

Apr 12th, 2019
167
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.  
  8.     Node(ll x):
  9.         left(NULL),
  10.         right(NULL),
  11.         x(x)
  12.         {}
  13. };
  14.  
  15.  
  16. Node* merge(Node *a, Node *b)
  17. {
  18.     if (a == NULL)
  19.         return b;
  20.     if (b == NULL)
  21.         return a;
  22.     if (a->x > b->x)
  23.         swap(a, b);
  24.     a->right = merge(a->right, b);
  25.     swap(a->right, a->left);
  26.     return a;
  27. }
  28.  
  29. Node* push(Node *root, ll x)
  30. {
  31.     return merge(root, new Node(x));
  32. }
  33.  
  34. Node* pop(Node *root)
  35. {
  36.     return merge(root->left, root->right);
  37. }
  38.  
  39. ll min(Node *root)
  40. {
  41.     return root->x;
  42. }
RAW Paste Data