posts - 183,  comments - 10,  trackbacks - 0
之前有借助于 STL 中的 multimap 实现查找最小的 k 个元素。
这里继续解决 查找最小的 k 个元素,采用 最大根堆。

  1 #include <iostream>
  2 #include <ctime>
  3 #include <vector>
  4 using namespace std;
  5 
  6 class Heap
  7 {
  8 private:
  9     int* data;
 10     int  _size;
 11     int  _capacity;
 12 public:
 13     Heap()
 14     {
 15         _size = 0;
 16         _capacity = 2 * _size;
 17         data = new int[_capacity];
 18         if (data == 0)
 19         {
 20             exit(1);
 21         }
 22     }
 23     Heap(const Heap& h)
 24     {
 25         _size = h._size;
 26         _capacity = h._capacity;
 27         data = new int[_capacity];
 28         if (data == 0)
 29         {
 30             exit(1);
 31         }
 32         memcpy(data, h.data, sizeof (int* h._size);
 33     }
 34     Heap& operator =(const Heap& h)
 35     {
 36         delete [] data;
 37         _size = h._size;
 38         _capacity = h._capacity;
 39         data = new int[_capacity];
 40         if (data == 0)
 41         {
 42             exit(1);
 43         }
 44         memcpy(data, h.data, sizeof (int* h._size);
 45     }
 46     ~Heap()
 47     {
 48         delete [] data;
 49     }
 50     void insert(int item)
 51     {
 52         if (_size >= _capacity - 1)
 53         {
 54             _capacity = (_capacity + 1* 2;
 55             int * tmp = new int[_capacity];
 56             if (tmp == 0)
 57             {
 58                 exit(1);
 59             }
 60             // 1
 61             memcpy(tmp, data, sizeof (int* _capacity / 2 - 1);
 62             delete [] data;
 63             data = tmp;
 64         }
 65         data[++_size] = item;
 66         int pos1 = _size;
 67         int pos2 = pos1 / 2;
 68         while (pos2 >= 1 && data[pos1] > data[pos2])
 69         {
 70             data[pos1] ^= data[pos2];
 71             data[pos2] ^= data[pos1];
 72             data[pos1] ^= data[pos2];
 73             pos1 = pos2;
 74             pos2 = pos1 / 2;
 75         }
 76     }
 77     int max()
 78     {
 79         return data[1];
 80     }
 81     int erase()
 82     {
 83         int tmp = data[1];
 84         data[1= data[_size];
 85         --_size;
 86         int pos1 = 1, pos2;
 87         pos2 = pos1 * 2;
 88         
 89         while (pos2 <= _size)
 90         {
 91             if (pos2 < _size && data[pos2 + 1> data[pos2])
 92             {
 93                 ++pos2;
 94             }
 95             if (data[pos1] < data[pos2])
 96             {
 97                 data[pos1] ^= data[pos2];
 98                 data[pos2] ^= data[pos1];
 99                 data[pos1] ^= data[pos2];
100             }
101             pos1 = pos2;
102             pos2 = pos1 * 2;
103         }
104         return tmp;
105     }
106     int size()
107     {
108         return _size;
109     }
110     int capacity()
111     {
112         return _capacity;
113     }
114     void test()
115     {
116         for (int i = 1; i <= _size; ++i)
117         {
118             cout << data[i] << ' ';
119         }
120         cout << endl;
121     }
122 };
123 
124 void findMinK(Heap& h, int k, const vector<int>& data)
125 {
126     int m = 0;
127     for (vector<int>::const_iterator cit = data.begin(); cit != data.end(); ++cit)
128     {
129         if (m < k)
130         {
131             h.insert(*cit);
132             ++m;
133         }
134         else
135         {
136             if (*cit < h.max())
137             {
138                 h.erase();
139                 h.insert(*cit);
140             }
141         }
142     }
143 }
144 
145 int main()
146 {
147     int n = 100;
148     Heap h;
149     vector<int> data;
150     srand(time(0));
151     while (n--)
152     {
153         data.push_back(rand());
154     }
155     findMinK(h, 10, data);
156     for (vector<int>::const_iterator cit = data.begin(); cit != data.end(); ++cit)
157     {
158         cout << *cit << ' ';
159     }
160     cout << endl;
161     for (int i = 0; i < 10++i)
162     {
163         cout << h.erase() << endl;
164     }
165     cout << endl;
166     return 0;
167 }
posted on 2011-04-27 00:03 unixfy 阅读(227) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理