-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathheap.hpp
More file actions
48 lines (41 loc) · 1.33 KB
/
heap.hpp
File metadata and controls
48 lines (41 loc) · 1.33 KB
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
#ifndef HEAP_HPP_INCLUDED
#define HEAP_HPP_INCLUDED
#include "common.hpp"
namespace AP
{
namespace algorithms
{
using std::swap;
template <typename Iterator>
void sift_down(const Iterator begin, const Iterator end, const Iterator start)
{
auto position = std::distance(begin, start);
// is equivalent to left_child = begin[ start*2 + 1];
Iterator left_child = std::next(start, position + 1 );
Iterator right_child = std::next(start, position + 2 );
if ( right_child >= end )
return;
if ( *start > *left_child )
{
swap(*start, *left_child);
sift_down(begin, end, left_child);
}
if ( *start > *right_child )
{
swap(*start, *right_child);
sift_down(begin, end, right_child);
}
}
template <typename Iterator>
void make_heap(const Iterator &begin, const Iterator end)
{
Iterator middle = get_middle(begin, end, typename std::iterator_traits<Iterator>::iterator_category());
for ( Iterator i = middle; i != end; i++)
{
swap(*i, *begin);
sift_down(begin, end, begin);
}
}
}
}
#endif