Lesson of 21 February 2011

Example of heapsort ordering

The header file

File heapsort.hh

 1/*
 2//
 3// Heap Sort
 4//
 5//
 6//
 7*/
 8
 9void
10heapsort( double v[], unsigned size ) ;

Implementation

File heapsort.cc

 1// to compile on unix/OSX use
 2// g++ -c testDecoration.cc (for generation of testDecoration.o)
 3// g95 -c add.f             (for generation of test.o a fortran routine)
 4// g++ testDecoration.o add.o -o test
 5// ./test (to run)
 6//
 7
 8// include STL for swap
 9#include <algorithm>
10
11static
12inline
13unsigned
14father( unsigned son ) 
15{ return (son-1)>>1 ; }
16
17static
18inline
19unsigned
20left_son( unsigned father ) 
21{ return (father<<1)|1 ; } // equivalent to 2*father+1
22
23static
24inline
25unsigned
26right_son( unsigned father ) 
27{ return (father<<1)+2 ; } // equivalent to 2*father+2
28
29/*
30//
31// Build incrementally a heap.
32// Each element is inserted to the heap starting from 1 to size-1.
33*/
34static
35void
36make_heap( double v[], unsigned size ) {
37  for ( unsigned i = 1 ; i < size ; ++i ) {
38    // insert v[i] to the heap
39    for ( unsigned j = i ; j > 0 ; j = father(j) )
40      if ( v[j] > v[father(j)] ) std::swap( v[j], v[father(j)] ) ;
41      else                       break ;
42  }
43}
44
45/*
46// Given an heap of k+1 element drop root and store to the element a[k].
47*/
48static
49void
50drop( double v[], unsigned k ) {
51  double root = v[0] ; // maximum element
52  unsigned winner, i = 0 ;  
53  while ( (winner=left_son(i)) <= k ) { // check if winner is inside the heap
54    unsigned rs = right_son(i) ;
55    if ( rs <= k && v[winner] < v[rs] ) winner = rs ;
56    // move winner to the father
57    v[i] = v[winner] ;
58    i    = winner ;
59  }
60  // i is the insertion position for v[k] the last element of the heap.
61  // Now insert v[k] at position i
62  v[i] = v[k] ;
63  for ( unsigned j = i ; j > 0 ; j = father(j) )
64    if ( v[j] > v[father(j)] ) std::swap( v[j], v[father(j)] ) ;
65    else                       break ;
66  // copy root to v[k]
67  v[k] = root ;
68}
69
70void
71heapsort( double v[], unsigned size ) {
72  // build the heap
73  make_heap( v, size ) ;
74  // drop maximimum from the heap
75  while ( --size > 0 ) drop( v, size ) ;
76}
77
78// file heapsort.cc

Testing the sort

File test.cc

 1// to compile on unix/OSX use
 2// g++ test.cc heapsort.cc -o test
 3// ./test (to run)
 4//
 5
 6#include <iostream>
 7#include "heapsort.hh"
 8
 9#define GET_SIZE(A) (sizeof(A)/sizeof(A[0]))
10
11int
12main() {
13  double       a[] = {1, 2, 5, 32, -19, 2, 3, 9, 2, 2, 2, -3 } ;
14  unsigned const N = GET_SIZE(a) ;
15  
16  heapsort( a, N ) ;
17  
18  for ( unsigned i = 0 ; i < N ; ++i )
19    std::cout << "a[ " << i << " ] = " << a[i] << '\n' ;
20  return 0 ;
21}

Example of heapsort with template

The templated algorithm

File heapsortTemplate.hh

 1// to compile on unix/OSX use
 2// g++ -c testDecoration.cc (for generation of testDecoration.o)
 3// g95 -c add.f             (for generation of test.o a fortran routine)
 4// g++ testDecoration.o add.o -o test
 5// ./test (to run)
 6//
 7
 8// include STL for swap
 9#include <algorithm>
10
11static
12inline
13unsigned
14father( unsigned son ) 
15{ return (son-1)>>1 ; }
16
17static
18inline
19unsigned
20left_son( unsigned father ) 
21{ return (father<<1)|1 ; } // equivalent to 2*father+1
22
23static
24inline
25unsigned
26right_son( unsigned father ) 
27{ return (father<<1)+2 ; } // equivalent to 2*father+2
28
29/*
30//
31// Build incrementally a heap.
32// Each element is inserted to the heap starting from 1 to size-1.
33*/
34template <typename T>
35void
36make_heap( T v[], unsigned size ) {
37  for ( unsigned i = 1 ; i < size ; ++i ) {
38    // insert v[i] to the heap
39    for ( unsigned j = i ; j > 0 ; j = father(j) )
40      if ( v[j] > v[father(j)] ) std::swap( v[j], v[father(j)] ) ;
41      else                       break ;
42  }
43}
44
45/*
46// Given an heap of k+1 element drop root and store to the element a[k].
47*/
48template <typename T>
49void
50drop( T v[], unsigned k ) {
51  T root = v[0] ; // maximum element
52  unsigned winner, i = 0 ;  
53  while ( (winner=left_son(i)) <= k ) { // check if winner is inside the heap
54    unsigned rs = right_son(i) ;
55    if ( rs <= k && v[winner] < v[rs] ) winner = rs ;
56    // move winner to the father
57    v[i] = v[winner] ;
58    i    = winner ;
59  }
60  // i is the insertion position for v[k] the last element of the heap.
61  // Now insert v[k] at position i
62  v[i] = v[k] ;
63  for ( unsigned j = i ; j > 0 ; j = father(j) )
64    if ( v[j] > v[father(j)] ) std::swap( v[j], v[father(j)] ) ;
65    else                       break ;
66  // copy root to v[k]
67  v[k] = root ;
68}
69
70template <typename T>
71void
72heapsort( T v[], unsigned size ) {
73  // build the heap
74  make_heap( v, size ) ;
75  // drop maximimum from the heap
76  while ( --size > 0 ) drop( v, size ) ;
77}
78
79// file heapsort.cc

Testing the sort

File test1.cc

 1// to compile on unix/OSX use
 2// g++ test1.cc heapsort.cc -o test
 3// ./test (to run)
 4//
 5
 6#include <iostream>
 7#include "heapsortTemplate.hh"
 8
 9#define GET_SIZE(A) (sizeof(A)/sizeof(A[0]))
10
11int
12main() {
13  double       a[] = {1, 2, 5, 32, -19, 2, 3, 9, 2, 2, 2, -3 } ;
14  int          b[] = {1, 2, 5, 32, -19, 2, 3, 9, 2, 2, 2, -3 } ;
15  unsigned const Na = GET_SIZE(a) ;
16  unsigned const Nb = GET_SIZE(b) ;
17  
18  heapsort<double>( a, Na ) ;
19  heapsort<int>( b, Nb ) ;
20  
21  for ( unsigned i = 0 ; i < Na ; ++i )
22    std::cout << "a[ " << i << " ] = " << a[i] << '\n' ;
23  return 0 ;
24}

Example of heapsort with template instantiation

The templated algorithm

File heapsort2.hxx

 1//
 2// heapsort implementation
 3//
 4//
 5
 6#include <algorithm>
 7#include "heapsort2.hh"
 8
 9static
10inline
11unsigned
12father( unsigned son ) 
13{ return (son-1)>>1 ; }
14
15static
16inline
17unsigned
18left_son( unsigned father ) 
19{ return (father<<1)|1 ; } // equivalent to 2*father+1
20
21static
22inline
23unsigned
24right_son( unsigned father ) 
25{ return (father<<1)+2 ; } // equivalent to 2*father+2
26
27/*
28//
29// Build incrementally a heap.
30// Each element is inserted to the heap starting from 1 to size-1.
31*/
32template <typename T>
33void
34HeapSort<T>::make_heap( T v[], unsigned size ) {
35  for ( unsigned i = 1 ; i < size ; ++i ) {
36    // insert v[i] to the heap
37    for ( unsigned j = i ; j > 0 ; j = father(j) )
38      if ( v[j] > v[father(j)] ) std::swap( v[j], v[father(j)] ) ;
39      else                       break ;
40  }
41}
42
43/*
44// Given an heap of k+1 element drop root and store to the element a[k].
45*/
46template <typename T>
47void
48HeapSort<T>::drop( T v[], unsigned k ) {
49  T root = v[0] ; // maximum element
50  unsigned winner, i = 0 ;  
51  while ( (winner=left_son(i)) <= k ) { // check if winner is inside the heap
52    unsigned rs = right_son(i) ;
53    if ( rs <= k && v[winner] < v[rs] ) winner = rs ;
54    // move winner to the father
55    v[i] = v[winner] ;
56    i    = winner ;
57  }
58  // i is the insertion position for v[k] the last element of the heap.
59  // Now insert v[k] at position i
60  v[i] = v[k] ;
61  for ( unsigned j = i ; j > 0 ; j = father(j) )
62    if ( v[j] > v[father(j)] ) std::swap( v[j], v[father(j)] ) ;
63    else                       break ;
64  // copy root to v[k]
65  v[k] = root ;
66}
67
68template <typename T>
69void
70HeapSort<T>::sort( T v[], unsigned size ) {
71  // build the heap
72  make_heap( v, size ) ;
73  // drop maximimum from the heap
74  while ( --size > 0 ) drop( v, size ) ;
75}
76
77// file heapsort.cc

The header file

File heapsort2.hh

 1//
 2// heapsort implementation
 3//
 4//
 5
 6#ifndef HEAPSORT2_HH
 7#define HEAPSORT2_HH
 8
 9// put elements in a struct for explicit specialization
10template <typename T>
11class HeapSort {
12  static void make_heap( T v[], unsigned size ) ;
13  static void drop( T v[], unsigned k ) ;
14public:
15  static void sort( T v[], unsigned size ) ;
16} ;
17
18#endif

The explicit instantiation

File heapsort2.cc

1#include "heapsort2.hh"
2#include "heapsort2.hxx"
3
4// intantiate class HeapSort for double and int specialization
5template class HeapSort<double> ;
6template class HeapSort<int> ;

Testing the sort

File test2.cc

 1// to compile on unix/OSX use
 2// g++ test.cc heapsort.cc -o test
 3// ./test (to run)
 4//
 5
 6#include <iostream>
 7#include "heapsort2.hh"
 8
 9#define GET_SIZE(A) (sizeof(A)/sizeof(A[0]))
10
11int
12main() {
13  double       a[] = {1, 2, 5, 32, -19, 2, 3, 9, 2, 2, 2, -3 } ;
14  int          b[] = {1, 2, 5, 32, -19, 2, 3, 9, 2, 2, 2, -3 } ;
15  unsigned const Na = GET_SIZE(a) ;
16  unsigned const Nb = GET_SIZE(b) ;
17  
18  HeapSort<double>::sort( a, Na ) ;
19  HeapSort<int>::sort( b, Nb ) ;
20  
21  for ( unsigned i = 0 ; i < Na ; ++i )
22    std::cout << "a[ " << i << " ] = " << a[i] << '\n' ;
23  return 0 ;
24}