之前有借助于 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 閱讀(232)
評論(0) 編輯 收藏 引用