Algorithm:cartesian tree

http://baike.baidu.com/link?url=XUt5fXQ-JtFBM 0 UdKiGA 41_NWFvdFSFYwVsy 4 SVvCRRuEBvNkLfT 9 TgOtzsXvaOT 9 nuq_EzKJcO 0 gt 6 nXSLU_
ここに詳しい紹介があります。
一つのcoding testのテーマはあなたに一つのint nをあげます。一連のfloatの数は、現在の数からこの数の前のn個の数までの最大値をリアルタイムにプリントアウトしてください。n個の数がないと、前の数の最大値です。ここではcartesian tree、label記録は数の下付きで、pは数値を表します。挿入操作はlg(n)で、削除操作もlg(n)で、全体の複雑度はNlg(n)です。

  1 #include <iostream>

  2 #include <fstream>

  3 #include <cstdio>

  4 

  5 using namespace std;

  6 

  7 class treap_node 

  8 {

  9     public:

 10         int label;

 11         float p;

 12         treap_node *left;

 13         treap_node *right;

 14         treap_node()

 15         {

 16             left = NULL;

 17             right = NULL;

 18         }

 19 };

 20 

 21 class treap:treap_node

 22 {

 23     public:

 24         treap_node *root;

 25         treap()

 26         {

 27             root = NULL;

 28         }

 29         void treap_left_rotate(treap_node* &a)

 30         {

 31             treap_node *b = a->right;

 32             a->right = b->left;

 33             b->left = a;

 34             a = b;

 35         }

 36         void treap_right_rotate(treap_node* &a)

 37         {

 38             treap_node *b = a->left;

 39             a->left = b->right;

 40             b->right = a;

 41             a = b;

 42         }

 43         void treap_insert(treap_node* &a, int &label, float &p)

 44         {

 45             if (!a)

 46             {

 47                 a = new treap_node;

 48                 a->label = label;

 49                 a->p = p;

 50             }

 51             else if (label > a->label)

 52             {

 53                 treap_insert(a->right, label, p);

 54                 if (a->right->p > a->p)

 55                     treap_left_rotate(a);

 56             }

 57             else

 58             {

 59                 treap_insert(a->left, label, p);

 60                 if (a->left->p < a->p)

 61                     treap_right_rotate(a);

 62             }

 63         }

 64         void treap_delete_smallestP(treap_node* &a)

 65         {

 66             treap_node *p = a;

 67             treap_node *pre = NULL;

 68             while (p->left != NULL)

 69             {

 70                 pre = p;

 71                 p = p->left;

 72             }

 73             if (pre != NULL)

 74             {

 75                 pre->left = p->right;

 76             }

 77             else

 78                 a = p->right;

 79             return;

 80         }

 81         void plist(treap_node *a) 

 82         {

 83             if (a != NULL)

 84             {

 85                 cout << "(";

 86                 plist(a->left);

 87                 cout << a->label << "/" << a->p;

 88                 plist(a->right);

 89                 cout << ")";

 90             }

 91         }

 92 };

 93 

 94 int atoi(char *s) 

 95 {

 96     int ret = 0;

 97     while (*s != '\0') {

 98         ret = ret * 10 + (int)(*s - '0');

 99         s++;

100     }

101     return ret;

102 }

103 

104 int main(int argc, char **argv) 

105 {

106  if (argc != 3) {

107      cout << "invalid input" << endl;

108    return 1;

109  }

110  //cout << argv[1] << " " << argv[2] << endl;

111  ifstream fin(argv[2]);

112  if (!fin) {

113      cout << "unable to open the file" << endl;

114      return 1;

115  }

116  int n = atoi(argv[1]);

117  int count = 0;

118  treap *p = new treap;

119  float s;

120  while (fin >> s) {

121      cout << s << " ";

122      if (count >= n) 

123      {

124          p->treap_delete_smallestP(p->root);

125      }

126      p->treap_insert(p->root, count, s);

127      p->plist(p->root); 

128      cout << p->root->p << endl;

129      count++;

130  }

131  return 0;

132 }