# tag: cpp
from libcpp cimport bool
from libcpp.algorithm cimport make_heap, sort_heap, sort, partial_sort
from libcpp.vector cimport vector
# XXX should use std::greater, but I don't know how to wrap that.
cdef inline bool greater(int x, int y):
return x > y
def heapsort(l, bool reverse=False):
"""
>>> heapsort([3, 5, 1, 0, 2, 4])
[0, 1, 2, 3, 4, 5]
>>> heapsort([3, 5, 1, 0, 2, 4], reverse=True)
[5, 4, 3, 2, 1, 0]
"""
cdef vector[int] v = l
if reverse:
make_heap(v.begin(), v.end(), greater)
sort_heap(v.begin(), v.end(), greater)
else:
make_heap(v.begin(), v.end())
sort_heap(v.begin(), v.end())
return v
def partialsort(l, int k, reverse=False):
"""
>>> partialsort([4, 2, 3, 1, 5], k=2)[:2]
[1, 2]
>>> partialsort([4, 2, 3, 1, 5], k=2, reverse=True)[:2]
[5, 4]
"""
cdef vector[int] v = l
if reverse:
partial_sort(v.begin(), v.begin() + k, v.end(), greater)
else:
partial_sort(v.begin(), v.begin() + k, v.end())
return v
def stdsort(l, reverse=False):
"""
>>> stdsort([3, 2, 1, 4, 5])
[1, 2, 3, 4, 5]
>>> stdsort([3, 2, 1, 4, 5], reverse=True)
[5, 4, 3, 2, 1]
"""
cdef vector[int] v = l
if reverse:
sort(v.begin(), v.end(), greater)
else:
sort(v.begin(), v.end())
return v