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