16.3.12. Heapsort
Figure 16.12 demonstrates the Standard Library algorithms for performing the heapsort sorting algorithm, in which an array of elements is arranged into a data structure called a heap. For more information on Heapsort and for additional resources, see:
1 // Fig. 16.12: fig16_12.cpp
2 // Algorithms push_heap, pop_heap, make_heap and sort_heap.
3 #include <iostream>
4 #include <algorithm>
5 #include <array>
6 #include <vector>
7 #include <iterator>
8 using namespace std;
9
10 int main()
11 {
12 const size_t SIZE = 10;
13 array< int, SIZE > init = { 3, 100, 52, 77, 22, 31, 1, 98, 13, 40 };
14 array< int, SIZE > a( init ); // copy of init
15 ostream_iterator< int > output( cout, " " );
16
17 cout << "Array a before make_heap:
";
18 copy( a.cbegin(), a.cend(), output );
19
20 make_heap( a.begin(), a.end() ); // create heap from array a
21 cout << "Array a after make_heap:
";
22 copy( a.cbegin(), a.cend(), output );
23
24 sort_heap( a.begin(), a.end() ); // sort elements with sort_heap
25 cout << "Array a after sort_heap:
";
26 copy( a.cbegin(), a.cend(), output );
27
28 // perform the heapsort with push_heap and pop_heap
29 cout << "
Array init contains: ";
30 copy( init.cbegin(), init.cend(), output ); // display array init
31 cout << endl;
32
33 vector< int > v;
34
35 // place elements of array init into v and
36 // maintain elements of v in heap
37 for ( size_t i = 0; i < SIZE; ++i )
38 {
39 v.push_back( init[ i ] );
40 push_heap( v.begin(), v.end() );
41 cout << "
v after push_heap(init[" << i << "]): ";
42 copy( v.cbegin(), v.cend(), output );
43 } // end for
44
45 cout << endl;
46
47 // remove elements from heap in sorted order
48 for ( size_t j = 0; j < v.size(); ++j )
49 {
50 cout << "
v after " << v[ 0 ] << " popped from heap
";
51 pop_heap( v.begin(), v.end() - j );
52 copy( v.cbegin(), v.cend(), output );
53 } // end for
54
55 cout << endl;
56 } // end main
Array a before make_heap:
3 100 52 77 22 31 1 98 13 40
Array a after make_heap:
100 98 52 77 40 31 1 3 13 22
Array a after sort_heap:
1 3 13 22 31 40 52 77 98 100
Array init contains: 3 100 52 77 22 31 1 98 13 40
v after push_heap(init[0]): 3
v after push_heap(init[1]): 100 3
v after push_heap(init[2]): 100 3 52
v after push_heap(init[3]): 100 77 52 3
v after push_heap(init[4]): 100 77 52 3 22
v after push_heap(init[5]): 100 77 52 3 22 31
v after push_heap(init[6]): 100 77 52 3 22 31 1
v after push_heap(init[7]): 100 98 52 77 22 31 1 3
v after push_heap(init[8]): 100 98 52 77 22 31 1 3 13
v after push_heap(init[9]): 100 98 52 77 40 31 1 3 13 22
v after 100 popped from heap
98 77 52 22 40 31 1 3 13 100
v after 98 popped from heap
77 40 52 22 13 31 1 3 98 100
v after 77 popped from heap
52 40 31 22 13 3 1 77 98 100
v after 52 popped from heap
40 22 31 1 13 3 52 77 98 100
v after 40 popped from heap
31 22 3 1 13 40 52 77 98 100
v after 31 popped from heap
22 13 3 1 31 40 52 77 98 100
v after 22 popped from heap
13 1 3 22 31 40 52 77 98 100
v after 13 popped from heap
3 1 13 22 31 40 52 77 98 100
v after 3 popped from heap
1 3 13 22 31 40 52 77 98 100
v after 1 popped from heap
1 3 13 22 31 40 52 77 98 100
Fig. 16.12. Algorithms push_heap, pop_heap, make_heap and sort_heap.
make_heap Algorithm
Line 20 uses the make_heap algorithm to take a sequence of values in the range from a.begin() up to, but not including, a.end() and create a heap that can be used to produce a sorted sequence. The two iterator arguments must be random-access iterators, so this algorithm will work only with arrays, vectors and deques. A second version of this algorithm takes as a third argument a binary predicate function for comparing values.
sort_heap Algorithm
Line 24 uses the sort_heap algorithm to sort a sequence of values in the range from a.begin() up to, but not including, a.end() that are already arranged in a heap. The two iterator arguments must be random-access iterators. A second version of this algorithm takes as a third argument a binary predicate function for comparing values.
push_heap Algorithm
Line 40 uses the push_heap algorithm to add a new value into a heap. We take one element of array init at a time, append it to the end of vector v and perform the push_heap operation. If the appended element is the only element in the vector, the vector is already a heap. Otherwise, push_heap rearranges the vector elements into a heap. Each time push_heap is called, it assumes that the last element currently in the vector (i.e., the one that’s appended before the push_heap call) is the element being added to the heap and that all other elements in the vector are already arranged as a heap. The two iterator arguments to push_heap must be random-access iterators. A second version of this algorithm takes as a third argument a binary predicate function for comparing values.
pop_heap Algorithm
Line 51 uses pop_heap to remove the top heap element. This algorithm assumes that the elements in the range specified by its two random-access iterator arguments are already a heap. Repeatedly removing the top heap element results in a sorted sequence of values. Algorithm pop_heap swaps the first heap element (v.begin()) with the last heap element (the element before v.end() - j), then ensures that the elements up to, but not including, the last element still form a heap. Notice in the output that, after the pop_heap operations, the vector is sorted in ascending order. A second version of this algorithm takes as a third argument a binary predicate function for comparing values.
C++11: is_heap and is_heap_until Algorithms
In addition to the make_heap, sort_heap, push_heap and pop_heap algorithms presented in Fig. 16.12, C++11 now includes the new algorithms is_heap and is_heap_until. The is_heap algorithm returns true if the elements in the specified range represent a heap. A second version of this algorithm takes as a third argument a binary predicate function for comparing values.
The is_heap_until algorithm checks the specified range of values and returns an iterator pointing to the last item in the range for which the elements up to, but not including, that iterator represent a heap.