cython

1
# mode: run
2
# tag: cpp
3

4
from libcpp cimport bool
5
from libcpp.algorithm cimport make_heap, sort_heap
6
from libcpp.vector cimport vector
7

8

9
# XXX should use std::greater, but I don't know how to wrap that.
10
cdef inline bool greater(const int &x, const int &y):
11
    return x > y
12

13

14
def heapsort(l, bool reverse=False):
15
    """
16
    >>> heapsort([3, 5, 1, 0, 2, 4])
17
    [0, 1, 2, 3, 4, 5]
18
    >>> heapsort([3, 5, 1, 0, 2, 4], reverse=True)
19
    [5, 4, 3, 2, 1, 0]
20
    """
21
    cdef vector[int] v = l
22

23
    if reverse:
24
        make_heap(v.begin(), v.end(), &greater)
25
        sort_heap(v.begin(), v.end(), &greater)
26
    else:
27
        make_heap(v.begin(), v.end())
28
        sort_heap(v.begin(), v.end())
29

30
    return v
31