fork download
copy 
  1. /*
  2.   Copyright 2013 Marek "p2004a" Rusinowski
  3.   Leftist Heap
  4. */
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <ctime>
  8.  
  9. #include <algorithm>
  10. #include <functional>
  11.  
  12. using namespace std;
  13.  
  14. template <class T, class Compare = less<T> >
  15. class LeftistHeap {
  16.  public:
  17.   class LeftistHeapNode {
  18.    public:
  19.     T value;
  20.     LeftistHeapNode *left, *right;
  21.     int s;
  22.  
  23.     LeftistHeapNode(T vvalue, LeftistHeapNode *lleft, LeftistHeapNode *rright, int ss)
  24.      : value(vvalue), left(lleft), right(rright), s(ss) {}
  25.  
  26.     LeftistHeapNode(const LeftistHeapNode &node) : value(node.value), left(NULL), right(NULL), s(node.s) {
  27.       if (node.left != NULL) left = new LeftistHeapNode(*node.left);
  28.       if (node.right != NULL) right = new LeftistHeapNode(*node.right);
  29.     }
  30.  
  31.     ~LeftistHeapNode() {
  32.       delete left;
  33.       delete right;
  34.     }
  35.   };
  36.  
  37.   LeftistHeapNode *merge(LeftistHeapNode *h1, LeftistHeapNode *h2) {
  38.     if (h1 == NULL) return h2;
  39.     if (h2 == NULL) return h1;
  40.     if (!cmp(h1->value, h2->value)) swap(h1, h2);
  41.     if (h1->left == NULL) h1->left = h2;
  42.     else {
  43.       h1->right = merge(h1->right, h2);
  44.       if (h1->left->s < h1->right->s) swap(h1->left, h1->right);
  45.       h1->s = h1->right->s + 1;
  46.     }
  47.     return h1;
  48.   }
  49.  
  50.  private:
  51.   LeftistHeapNode *root;
  52.   size_t heap_size;
  53.   Compare cmp;
  54.  
  55.  public:
  56.   LeftistHeap() : root(NULL), heap_size(0) {}
  57.  
  58.   LeftistHeap(const LeftistHeap &heap) : root(NULL), heap_size(heap.heap_size) {
  59.     if (heap.root != NULL) root = new LeftistHeapNode(*heap.root);
  60.   }
  61.  
  62.   ~LeftistHeap() {
  63.     delete root;
  64.   }
  65.  
  66.   LeftistHeap &operator=(const LeftistHeap &heap) {
  67.     delete root;
  68.     root = new LeftistHeapNode(*heap.root);
  69.     heap_size = heap.heap_size;
  70.     return *this;
  71.   }
  72.  
  73.   LeftistHeapNode *insert(T value) {
  74.     LeftistHeapNode *node = new LeftistHeapNode(value, NULL, NULL, 0);
  75.     root = merge(root, node);
  76.     ++heap_size;
  77.     return node;
  78.   }
  79.  
  80.   T top() {
  81.     if (root == NULL) throw "Cannot get min from empty heap";
  82.     return root->value;
  83.   }
  84.  
  85.   T deltop() {
  86.     if (root == NULL) throw "Cannot del min from empty heap";
  87.     LeftistHeapNode *tmp = root;
  88.     root = merge(root->left, root->right);
  89.     --heap_size;
  90.     tmp->left = tmp->right = NULL;
  91.     T value = tmp->value;
  92.     delete tmp;
  93.     return value;
  94.   }
  95.  
  96.   void merge(LeftistHeap &heap) {
  97.     root = merge(root, heap.root);
  98.     heap_size += heap.heap_size;
  99.     heap.root = NULL;
  100.     heap.heap_size = 0;
  101.   }
  102.  
  103.   size_t size() {
  104.     return heap_size;
  105.   }
  106. };
  107.  
  108. inline int los(int a, int b) {
  109.   return rand() % (b - a + 1) + a;
  110. }
  111.  
  112. int main() {
  113.   srand(time(NULL));
  114.   LeftistHeap<int> heap1, heap2, heap3;
  115.   int n = 20;
  116.   for (int i = 0; i < n; ++i) {
  117.     heap1.insert(los(1, 200));
  118.     heap2.insert(los(1, 200));
  119.   }
  120.   heap3 = heap2;
  121.   heap1.merge(heap2);
  122.   heap1.merge(heap3);
  123.   while (heap1.size() > 0) {
  124.     printf("%d ", heap1.deltop());
  125.   }
  126.   printf("\n");
  127.   return 0;
  128. }
  129.  
Success #stdin #stdout 0s 3032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 2 3 11 22 22 26 26 26 26 39 39 42 42 47 47 57 57 67 69 71 77 77 85 87 91 93 93 98 104 105 108 108 111 111 119 121 121 135 138 138 141 141 147 147 152 154 155 170 170 172 172 182 182 190 195 195 195 197 197
https://ideone.com/DxzoDl
Leftist Heap
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!