Skip to content

Commit 1c8f32f

Browse files
rudi8848rudi8848
committed
min heap
1 parent 8f79273 commit 1c8f32f

3 files changed

Lines changed: 255 additions & 1 deletion

File tree

‎1/window.c‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -65,7 +65,6 @@ struct MaxQueue
6565
{
6666
int tmp = _left.top();
6767
_left.pop();
68-
//std::cout << "push right " << tmp << std::endl;
6968
_right.push(tmp);
7069
}
7170
}

‎2/max_heap.cpp‎

Lines changed: 137 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,137 @@
1+
#include <iostream>
2+
#include <vector>
3+
#include <climits>
4+
5+
class MaxHeap
6+
{
7+
public:
8+
MaxHeap(std::vector<int> &v) {
9+
_size = v.size();
10+
_heap = v;
11+
for (int i = _size / 2 +1 ; i > -1 ; --i)
12+
SiftDown(i);
13+
_maxSize = _heap.capacity();
14+
}
15+
~MaxHeap() {}
16+
17+
int Parent(int i) { return (i - 1) / 2; }
18+
int LeftChild(int i) { return 2 * i + 1; }
19+
int RightChild(int i) { return 2 * i + 2; }
20+
int size() { return _size; }
21+
int maxSize() { return _maxSize; }
22+
23+
void SiftUp(int i) {
24+
while (i > 0 && _heap[Parent(i)] < _heap[i])
25+
{
26+
std::swap(_heap[Parent(i)], _heap[i]);
27+
i = Parent(i);
28+
}
29+
}
30+
31+
void SiftDown(int i) {
32+
int maxIndex = i;
33+
int l = LeftChild(i);
34+
35+
if (l < _size && _heap[l] > _heap[maxIndex])
36+
maxIndex = l;
37+
38+
int r = RightChild(i);
39+
if (r < _size && _heap[r] > _heap[maxIndex])
40+
maxIndex = r;
41+
42+
if (i != maxIndex)
43+
{
44+
std::swap(_heap[i], _heap[maxIndex]);
45+
SiftDown(maxIndex);
46+
}
47+
}
48+
49+
void Insert(int p) {
50+
if (_size == _maxSize) {
51+
std::cout << "Max size!";
52+
return;
53+
}
54+
++_size;
55+
_heap[_size - 1] = p;
56+
SiftUp(_size -1);
57+
}
58+
59+
int ExtractMax() {
60+
int result = _heap[0];
61+
_heap[0] = _heap[_size -1];
62+
--_size;
63+
SiftDown(0);
64+
return result;
65+
}
66+
67+
void Remove(int i) {
68+
_heap[i] = INT_MAX;
69+
SiftUp(i);
70+
ExtractMax();
71+
}
72+
73+
void ChangePriority(int i, int p) {
74+
int oldp = _heap[i];
75+
_heap[i] = p;
76+
if (p > oldp)
77+
SiftUp(i);
78+
else
79+
SiftDown(i);
80+
}
81+
82+
std::vector<int> const & heap() { return _heap; }
83+
84+
private:
85+
std::vector<int> _heap;
86+
int _size;
87+
int _maxSize;
88+
89+
};
90+
91+
92+
int main(void) {
93+
94+
std::vector<int> v = {7, 11, 29, 12, 42, 18, 13, 18, 14};
95+
for (int i = 0; i < v.size(); ++i)
96+
std::cout << v[i] << " ";
97+
std::cout << std::endl;
98+
99+
MaxHeap h(v);
100+
101+
for (int i = 0; i < h.size(); ++i)
102+
std::cout << h.heap()[i] << " ";
103+
std::cout << std::endl;
104+
105+
106+
std::cout << "\t\t\t" <<h.heap()[0] << std::endl;
107+
std::cout << "\t\t" << h.heap()[h.LeftChild(0)] << "\t\t" << h.heap()[h.RightChild(0)] << std::endl;
108+
std::cout << "\t"<< h.heap()[h.LeftChild(h.LeftChild(0))] << "\t" << h.heap()[h.RightChild(h.LeftChild(0))] << "\t\t" <<
109+
h.heap()[h.LeftChild(h.RightChild(0))] << "\t" << h.heap()[h.RightChild(h.RightChild(0))] << std::endl;
110+
std::cout << h.heap()[h.LeftChild(h.LeftChild(h.LeftChild(0)))] << "\t" << h.heap()[h.RightChild(h.LeftChild(h.LeftChild(0)))] << std::endl<< std::endl;
111+
112+
h.ExtractMax();
113+
114+
for (int i = 0; i < h.size(); ++i)
115+
std::cout << h.heap()[i] << " ";
116+
std::cout << std::endl;
117+
std::cout << "\t\t\t" <<h.heap()[0] << std::endl;
118+
std::cout << "\t\t" << h.heap()[h.LeftChild(0)] << "\t\t" << h.heap()[h.RightChild(0)] << std::endl;
119+
std::cout << "\t"<< h.heap()[h.LeftChild(h.LeftChild(0))] << "\t" << h.heap()[h.RightChild(h.LeftChild(0))] << "\t\t" <<
120+
h.heap()[h.LeftChild(h.RightChild(0))] << "\t" << h.heap()[h.RightChild(h.RightChild(0))] << std::endl;
121+
std::cout << h.heap()[h.LeftChild(h.LeftChild(h.LeftChild(0)))] << std::endl<< std::endl;
122+
123+
124+
h.Insert(58);
125+
126+
for (int i = 0; i < h.size(); ++i)
127+
std::cout << h.heap()[i] << " ";
128+
std::cout << std::endl;
129+
130+
std::cout << "\t\t\t" <<h.heap()[0] << std::endl;
131+
std::cout << "\t\t" << h.heap()[h.LeftChild(0)] << "\t\t" << h.heap()[h.RightChild(0)] << std::endl;
132+
std::cout << "\t"<< h.heap()[h.LeftChild(h.LeftChild(0))] << "\t" << h.heap()[h.RightChild(h.LeftChild(0))] << "\t\t" <<
133+
h.heap()[h.LeftChild(h.RightChild(0))] << "\t" << h.heap()[h.RightChild(h.RightChild(0))] << std::endl;
134+
std::cout << h.heap()[h.LeftChild(h.LeftChild(h.LeftChild(0)))] << "\t" << h.heap()[h.RightChild(h.LeftChild(h.LeftChild(0)))] << std::endl<< std::endl;
135+
136+
return 0;
137+
}

‎2/min_heap.cpp‎

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,118 @@
1+
#include <iostream>
2+
#include <vector>
3+
4+
class MinHeap
5+
{
6+
public:
7+
MinHeap(std::vector<int> &v) {
8+
_size = v.size();
9+
_heap = v;
10+
for (int i = _size / 2 + 1 ; i > -1 ; --i)
11+
SiftDown(i);
12+
_maxSize = _heap.capacity();
13+
}
14+
~MinHeap() {}
15+
16+
int Parent(int i) { return (i - 1) / 2; }
17+
int LeftChild(int i) { return 2 * i + 1; }
18+
int RightChild(int i) { return 2 * i + 2; }
19+
int size() { return _size; }
20+
int maxSize() { return _maxSize; }
21+
/*
22+
void SiftUp(int i) {
23+
while (i > 0 && _heap[Parent(i)] > _heap[i])
24+
{
25+
_log.push_back(std::make_pair(_heap[Parent(i)], _heap[i]));
26+
std::swap(_heap[Parent(i)], _heap[i]);
27+
i = Parent(i);
28+
}
29+
}
30+
*/
31+
void SiftDown(int i) {
32+
int minIndex = i;
33+
int l = LeftChild(i);
34+
35+
if (l < _size && _heap[l] < _heap[minIndex])
36+
minIndex = l;
37+
38+
int r = RightChild(i);
39+
if (r < _size && _heap[r] < _heap[minIndex])
40+
minIndex = r;
41+
42+
if (i != minIndex)
43+
{
44+
_log.push_back(std::make_pair(i, minIndex));
45+
std::swap(_heap[i], _heap[minIndex]);
46+
SiftDown(minIndex);
47+
}
48+
}
49+
/*
50+
void Insert(int p) {
51+
if (_size == _maxSize) {
52+
std::cout << "Max size!";
53+
return;
54+
}
55+
++_size;
56+
_heap[_size - 1] = p;
57+
SiftUp(_size - 1);
58+
}
59+
60+
int ExtractMin() {
61+
int result = _heap[0];
62+
_heap[0] = _heap[_size - 1];
63+
--_size;
64+
SiftDown(0);
65+
return result;
66+
}
67+
68+
void Remove(int i) {
69+
_heap[i] = -1;
70+
SiftUp(i);
71+
ExtractMin();
72+
}
73+
74+
void ChangePriority(int i, int p) {
75+
int oldp = _heap[i];
76+
_heap[i] = p;
77+
if (p < oldp)
78+
SiftUp(i);
79+
else
80+
SiftDown(i);
81+
}
82+
*/
83+
std::vector<int> const & heap() { return _heap; }
84+
std::vector<std::pair<int, int>> const & log() { return _log;}
85+
86+
private:
87+
std::vector<int> _heap;
88+
89+
int _size;
90+
int _maxSize;
91+
std::vector<std::pair<int, int>> _log;
92+
};
93+
94+
95+
int main(void)
96+
{
97+
int n;
98+
99+
std::cin >> n;
100+
101+
std::vector<int> v(n);
102+
for (int i = 0; i < n; ++i)
103+
std::cin >> v[i];
104+
105+
MinHeap heap(v);
106+
107+
for (int i = 0; i < n; ++i)
108+
std::cout << heap.heap()[i] << " ";
109+
std::cout << std::endl;
110+
111+
std::cout << heap.log().size() << std::endl;
112+
if (heap.log().size()) {
113+
for (int i = 0; i < heap.log().size(); ++i) {
114+
std::cout << heap.log()[i].first << " " << heap.log()[i].second << std::endl;
115+
}
116+
}
117+
return 0;
118+
}

0 commit comments

Comments
 (0)