blob: 4e54d633accb9f0da3330d96efe49ab79de2fbe8 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
#pragma once
#include <vector>
#include <stdexcept>
class priority_queue
{
private:
static size_t left_child(size_t index);
static size_t right_child(size_t index);
static int parent(int index);
void heapify(size_t index);
public:
priority_queue() = default;
// build_heap
priority_queue(const std::vector<int>& data);
void push(int element);
int peek() const;
void pop();
bool empty() const;
size_t size() const;
private:
std::vector<int> _data;
};
size_t priority_queue::left_child(size_t index)
{
return 2 * index + 1;
}
size_t priority_queue::right_child(size_t index)
{
return 2 * index + 2;
}
int priority_queue::parent(int index)
{
return (index - 1) / 2;
}
void priority_queue::heapify(size_t index)
{
size_t current_index = index;
while(true)
{
size_t left_index = left_child(current_index);
size_t right_index = right_child(current_index);
bool go_left = left_index < _data.size() && _data[current_index] < _data[left_index];
bool go_right = right_index < _data.size() && _data[current_index] < _data[right_index];
if(!go_left && !go_right)
{
break;
}
if(go_left && go_right)
{
if(_data[left_index] > _data[right_index])
{
std::swap(_data[current_index], _data[left_index]);
current_index = left_index;
}
else
{
std::swap(_data[current_index], _data[right_index]);
current_index = right_index;
}
}
else if(go_left)
{
std::swap(_data[current_index], _data[left_index]);
current_index = left_index;
}
else // go_right
{
std::swap(_data[current_index], _data[right_index]);
current_index = right_index;
}
}
}
priority_queue::priority_queue(const std::vector<int>& data) :
_data(data)
{
// build_heap
for (int i = _data.size() / 2 - 1; i >= 0; i--)
heapify(i);
}
void priority_queue::push(int element)
{
_data.push_back(element);
int index = _data.size() - 1;
int parent_index = parent(index);
while(index > 0 && _data[index] > _data[parent_index])
{
std::swap(_data[index], _data[parent_index]);
index = parent_index;
parent_index = parent(index);
}
}
int priority_queue::peek() const
{
return _data[0];
}
void priority_queue::pop()
{
if(empty())
throw std::runtime_error("Pop on empty queue");
_data[0] = _data.back();
_data.pop_back();
heapify(0);
}
size_t priority_queue::size() const
{
return _data.size();
}
bool priority_queue::empty() const
{
return size() == 0;
}
|
