-
Notifications
You must be signed in to change notification settings - Fork 0
/
heap_c.pxd
96 lines (71 loc) · 1.89 KB
/
heap_c.pxd
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
ctypedef struct heap_c:
size_t capacity
size_t size
size_t* items
cdef extern size_t _lzcnt_u64 (size_t x)
cdef inline void _swap(size_t* a, size_t i, size_t j):
cdef size_t tmp
tmp = a[i]
a[i] = a[j]
a[j] = tmp
cdef inline size_t log2_loop(size_t x):
cdef:
size_t i = 0
size_t c = 1
if x == 0:
return 0
while c <= x:
c *= 2
i += 1
return i - 1
cdef inline size_t log2(size_t x):
if x == 0:
return 0
return 63 - _lzcnt_u64(x)
cdef inline size_t _get_level(size_t i):
return log2(i + 1)
cdef inline size_t get_parent_h(size_t i):
# idx // 2
return ((i + 1) >> 1) - 1
cdef inline size_t _get_l_child(size_t i):
# idx * 2
return (i << 1) + 1
cdef inline bint is_full_h(heap_c* h):
return h.size == h.capacity
cdef inline bint is_empty_h(heap_c* h):
return h.size == 0
cdef inline size_t _min3(size_t a1, size_t a2, size_t a3):
if a1 < a2 and a1 < a3:
return a1
elif a2 < a3:
return a2
return a3
cdef inline (size_t, size_t) get_children(size_t h_size, size_t i):
"""
Return left and right child index. In case doesn't exist - return -1.
:param h_size: heap size
:param i: item index
:return: left, right children indexes.
"""
cdef size_t l_idx = _get_l_child(i)
if l_idx > h_size - 1:
return -1, -1
elif l_idx == h_size - 1:
return l_idx, -1
else:
return l_idx, l_idx + 1
cdef inline size_t get_child_cnt(size_t h_size, size_t i):
cdef size_t l, r
l, r = get_children(h_size, i)
if l == -1:
return 0
if r == -1:
return 1
else:
return 2
cdef:
heap_c* create_heap(size_t n)
void push_heap(heap_c * h, size_t x)
size_t pop_heap(heap_c * h)
void free_heap(heap_c * h)
void print_heap(heap_c * h, size_t i=*, str indent=*, bint last=*)