/*
* This example program show's C++'s provided heap data structure, and how
* to use it to sort a vector of integers. We do some timing experiments
* to see how long it takes to sort a vector of 1 million integers, and
* compare that to the time it takes to sort the same vector using the
* std::sort and std::stable_sort algorithms.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <random>
#include <chrono>
#include <iomanip>
#include <cassert>
void printVector(const std::vector<int>& vec) {
// Prints the first four and last four elements of a vector, separated
// by commas, with an elipsis in the middle. We assume the vector has
// more than eight elements.
constexpr size_t SHOWLEN = 4;
assert(vec.size() > 2 * SHOWLEN);
for (size_t i = 0; i < SHOWLEN; ++i) {
std::cout << vec[i] << ", ";
}
std::cout << "... ";
size_t size = vec.size();
for (size_t i = size - SHOWLEN; i < size; ++i) {
std::cout << ", " << vec[i];
}
std::cout << std::endl;
}
int main() {
// Create a vector of 5 million random integers.
constexpr size_t N = 5000000;
std::vector<int> data;
data.reserve(N);
std::random_device rd;
std::seed_seq seed{rd(),rd(),rd(),rd()};
std::mt19937 rng(seed);
for (size_t i = 0; i < N; ++i) {
data.push_back(i);
}
// Shuffle the vector.
std::shuffle(data.begin(), data.end(), rng);
std::cout << N << " random integers generated:\n ";
printVector(data);
// Make a duplicate of the vector, so we can sort it using std::sort
std::vector<int> sortMe = data;
// Sort the vector using std::sort.
auto start = std::chrono::high_resolution_clock::now();
std::sort(sortMe.begin(), sortMe.end());
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> elapsed = end - start;
std::cout << "std::sort took " << std::fixed << std::setprecision(3)
<< elapsed.count() << " seconds, result:\n ";
printVector(sortMe);
// Do it all again for std::stable_sort.
sortMe = data;
start = std::chrono::high_resolution_clock::now();
std::stable_sort(sortMe.begin(), sortMe.end());
end = std::chrono::high_resolution_clock::now();
elapsed = end - start;
std::cout << "std::stable_sort took " << std::fixed << std::setprecision(3)
<< elapsed.count() << " seconds, result:\n ";
printVector(sortMe);
// C++ does not provide a std::heap<T> data structure, instead it provides
// some algorithms that operate on a vector of elements (or something
// vector-like). These are std::make_heap, std::push_heap, std::pop_heap,
// and std::sort_heap.
// std::make_heap
// Heapifies a vector of elements, so that the largest element is
// at the front of the vector (a max-heap).
// std::push_heap
// Adds a new element to the heap, and reorders the heap so that
// the largest element is at the front of the vector.
// std::pop_heap
// Removes the largest element from the heap, and reorders the heap
// so that the largest element is at the front of the vector. The
// largest element is not removed from the vector, but is moved to
// just past the end of the heap area in the vector.
// std::sort_heap
// Sorts a heapified vector of elements, so that the elements are
// in ascending order. It just repeatedly calls std::pop_heap.
// (For clarity, we don't use std::sort_heap in this example and
// instead call std::pop_heap repeatedly.)
// Sort the vector using std::make_heap, std::push_heap, and
// std::pop_heap.
sortMe = data;
start = std::chrono::high_resolution_clock::now();
auto heapStart = sortMe.begin();
auto heapEnd = sortMe.end();
std::make_heap(heapStart, heapEnd);
for (size_t i = 1; i < N; ++i) {
std::pop_heap(heapStart, heapEnd);
// The max element is now at the end of the heap area, and the heap
// area is one element smaller.
--heapEnd;
}
end = std::chrono::high_resolution_clock::now();
elapsed = end - start;
std::cout << "std::make_heap, std::push_heap, and std::pop_heap took "
<< std::fixed << std::setprecision(3) << elapsed.count()
<< " seconds, result:\n ";
printVector(sortMe);
return 0;
}
