Parametrisable heapsort in C++

Submitted by GaB on 2008, July 20 - 22:31

Type parameters (a.k.a. templates in C++) can be used to do crazy things. It is not just a feature improving type safety by making more checks possible at compile time, but it also extends the ways a programmer can express parametrization of classes. In the following example I demonstrate an algorithm that implements a heapsort, but expects three type parameters:

  • The type of some kind of random access iterator. The elements accessible through this are going to be sorted. This parameter is required, but can be guessed by the compiler.
  • The type of some kind of strict weak ordering. If this parameter is not present, the compiler will try to use the default operator< for the iterated elements ( std::less() ).
  • The type of some kind of index function used by heapsort. Here comes the funny part: it is possible to reuse this heapsort algorithm. For example you want order elements like the pipes of a lilac/orgel (the highest value is in the middle, others surround them in a descending order), you can simply specify an indexing here, so that the highest element is placed by this function in the middle instead of the head or tail the as heapsort does. In other words when heapsort refers to the n-th element, this is filtered through this index function. This way you can achieve sort patterns that you couldn't apply by using a different ordering function. The default is such one, the supplied lilacsorter. You would get the same result by applying heapsort and reordering the result afterwards using this index function, but this would take additionally up to O(n) time.

The type parameters are required to instantiate them (as a class or function) at runtime. Of course I could use some generic interface (a class with virtual functions). Using templates instead is more advanced because the compiler can check at compile time, whether the supplied arguments are of the correct type or not. It makes also possible for supplying the most general default values: the compiler can automatically guess the operator< for a type having one.

Here is the header heapsortplus.h:

1
2
3
4
56
7
8
9
1011
12
13
14
1516
17
18
19
2021
22
23
24
2526
27
28
29
3031
32
33
34
3536
37
38
39
4041
42
43
44
4546
47
48
49
5051
52
53
54
5556
57
58
59
6061
62
63
64
6566
67
68
69
7071
72
73
74
7576
77
78
79
8081
82
83
84
8586
87
88
89
9091
92
93
94
9596
97
98
99
100101
102
103
104
105106
107
108
109
110111
112
113
114
115116
117
118
119
120121
122
123
124
125126
127
128
129

/** @file heapsortplus.h                Templateable sorting functions for C++.
 *
 * With the heapsortplus function you can sort an arbitrary (random access) iterable 
 * set of elements. It uses the well known (and fast) heapsort algorithm for sorting.
 * You can specify the ordering operator.  * You can also specify a permutation (bijective relation) of the elements the iterator 
 * iterates on, so even with a standard ordering operator you can achieve special 
 * sorting results. In other ways this is an index function used by the sorter. For example
 * you can order the elements in a way, that the biggest elements are sorted to the 
 * centre, and the smaller ones to the left and right in descending order. There is no * ordering relation that would result in this ordering.
 */
 
#ifndef heapsortplus_h
#define heapsortplus_h 
/** heapsort's shiftdown function
 */
template <class RandomAccessIterator, class StrictWeakOrdering, class Indexer>
void shiftdown(RandomAccessIterator i,unsigned long int from, unsigned long int end,                                const StrictWeakOrdering& less,const Indexer& idx) {
        unsigned long int child, root = from;
        while ( root * 2 + 1 <= end ) {
                child = root * 2 + 1;
                if (child < end && less(i[idx(child+1)],i[idx(child)])) ++child;                if (less(i[idx(child)],i[idx(root)])) 
                        { std::swap(i[idx(child)],i[idx(root)]); root=child; } else return;
        }
}
 /** initializes the heap
 */
template <class RandomAccessIterator, class StrictWeakOrdering, class Indexer>
void heapify(RandomAccessIterator first,unsigned long int count,
                        const StrictWeakOrdering& less,const Indexer& idx) {        unsigned long int from = count / 2 - 1 + count % 2;
        shiftdown(first, from, count - 1,less,idx);
        while (from>0) {
                --from;
                shiftdown(first, from, count - 1,less,idx);        }
}
 
/** the sorter
 */template <class RandomAccessIterator,class StrictWeakOrdering,class Indexer>
void heapsortplus(RandomAccessIterator first,RandomAccessIterator end,
                                const StrictWeakOrdering& less,const Indexer& idx) {
        if (end-first<2) return;
        unsigned long int count=end-first;        unsigned long int last=count-1;
        heapify(first,count,less,idx);
        while (last > 0) {
                        std::swap(first[idx(0)],first[idx(last)]);
                        --last;                        shiftdown(first,0,last,less,idx);
        }
}
 
/** index relation to retain the ordering of the sort*/
template <class T, class D>
class minsorter {
        protected:
                T first,length;        public:
        minsorter(D f, D l) 
        {       
                first=f;
                length=l;        }
        inline T operator()(T x) const {
                return x;
        }
}; 
/** index relation to reverse the ordering of the sort
*/
template <class T, class D>
class maxsorter {        protected:
                D first,length;
        public:
        maxsorter(D f, D l) 
        {                       first=f;
                length=l;
        }
        inline T operator()(T x) const {
                return length-x-1;        }
};
 
/** index relation impossible to substitute with an ordering
*/template <class T, class D>
class lilacsorter {
        protected:
                D first,length;
        public:        lilacsorter(D f, D l) 
        {       
                first=f;
                length=l;
        }        inline T operator()(T x) const {
                return (length/2)-((x-first)%2==0?-1:1)*(x/2)-((x-first)%2==0?0:1);
        }
};
 /** use the default lilacsorter
*/
template <class RandomAccessIterator, class StrictWeakOrdering>
void heapsortplus(RandomAccessIterator first,RandomAccessIterator end, const StrictWeakOrdering& less) {
        heapsortplus(first,end,less,        lilacsorter<
                typename std::iterator_traits<RandomAccessIterator>::value_type,
                typename std::iterator_traits<RandomAccessIterator>::difference_type
        >(0,end-first));
} 
/** let the compiler guess the default ordering
*/
template <class RandomAccessIterator>
void heapsortplus(RandomAccessIterator first,RandomAccessIterator end) {        heapsortplus(first,end,std::less<typename RandomAccessIterator::value_type>());
}
 
#endif //heapsortplus_h

Here are some use cases:

1
2
3
4
56
7
8
9
1011
12
13
14
1516
17
18
19
2021
22
23
24
2526
27
28
29
3031
32
33
34
3536
37
38
39
4041
42
43
44
4546
47
48
49
5051
52
53
54
5556
57
58

#include <iostream>
#include "heapsortplus.h"
#include <vector>
 
using namespace std; 
// inverse sorting function
template<class T>
bool inverseless(T a,T b) {
        return !less<T>()(a,b);}
 
// special sorting fuction
bool myless(const int& a,const int& b) {
        return (a%2==0^b%2==0?b%2==0:a<b);}
 
int main() {
        srand(time(NULL));
        vector<int> v(23); 
        for (vector<int>::iterator i=v.begin();i!=v.end();++i) *i=random()%100;
        cout <<         "Original         : ";
        // 93 50 50 36 59 68 77 20 80 36 24 29 75 16 21 34 8 1 48 72 88 33 89
        for (vector<int>::iterator i=v.begin();i!=v.end();++i) cout << *i << " ";        cout << endl;
 
        heapsortplus(v.begin(),v.end());
        cout << endl << "Lilacsort        : ";
        // 8 20 24 33 36 48 50 68 75 80 89 93 88 77 72 59 50 36 34 29 21 16 1           for (vector<int>::iterator i=v.begin();i!=v.end();++i) cout << *i << " ";
        cout << endl;
 
        heapsortplus(v.begin(),v.end(),inverseless<int>);
        cout << endl << "InverseLilacsort : ";        // 89 80 75 68 50 48 36 33 24 20 8 1 16 21 29 34 36 50 59 72 77 88 93
        for (vector<int>::iterator i=v.begin();i!=v.end();++i) cout << *i << " ";
        cout << endl;
 
        heapsortplus(v.begin(),v.end(),std::less<int>(),minsorter<int,int>(0,v.size()));        cout << endl << "Minsort          : ";
        // 93 89 88 80 77 75 72 68 59 50 50 48 36 36 34 33 29 24 21 20 16 8 1
        for (vector<int>::iterator i=v.begin();i!=v.end();++i) cout << *i << " ";
        cout << endl;
         heapsortplus(v.begin(),v.end(),std::less<int>(),maxsorter<int,int>(0,v.size()));
        cout << endl << "Maxsort          : ";
        // 1 8 16 20 21 24 29 33 34 36 36 48 50 50 59 68 72 75 77 80 88 89 93
        for (vector<int>::iterator i=v.begin();i!=v.end();++i) cout << *i << " ";
        cout << endl; 
        heapsortplus(v.begin(),v.end(),myless,maxsorter<int,int>(0,v.size()));
        cout << endl << "My less's maxsort: ";
        // 1 21 29 33 59 75 77 89 93 8 16 20 24 34 36 36 48 50 50 68 72 80 88
        for (vector<int>::iterator i=v.begin();i!=v.end();++i) cout << *i << " ";        cout << endl;
        return 0;
}