code. compile. run. debug. share.
/*
* This is a demo of our heap class.
*
* This code also uses a C++ feature that we haven't discussed in
* the course, the C++11 "initializer list" syntax; see
* - https://en.cppreference.com/w/cpp/language/initializer_list
* and https://en.cppreference.com/w/cpp/utility/initializer_list
*/
#include "heap.hpp"
#include <iostream>
#include <vector>
#include <string>
/* In the last part of our example, we'll create a priority queue, so we'll
* make a simple struct to store a value and its priority.
*/
template <typename T>
struct Prioritized {
int priority;
T value;
};
// Comparison function for Prioritized<T> objects.
template <typename T>
bool operator<(const Prioritized<T>& lhs, const Prioritized<T>& rhs) {
return lhs.priority < rhs.priority;
}
// Print function for Prioritized<T> objects.
template <typename T>
std::ostream& operator<<(std::ostream& out, const Prioritized<T>& p) {
return out << p.priority << ":" << p.value;
}
int main() {
auto foodList = {"pizza", "tacos", "sushi", "pasta", "ramen",
"beans", "toast", "steak", "salad", "eggs"};
// ^-- This is C++11's "initializer list" syntax, which allows us to
// initialize a vector with a list of values. We can iterate over
// the list .begin() and .end() iterators, and access the underlying
// primitive array with .data().
std::vector<std::string> foods{foodList.begin(), foodList.end()};
std::cout << "## Complete tree (before heapify):\n\n";
Heap<std::string>::printCompleteTree(std::cout, foods);
std::cout << "\n## Heap (after heapify -- string comparison order):\n\n";
Heap<std::string> heap{foods}; // Performs a heapify operation
std::cout << heap << std::endl;
std::cout << "## Repeatedly popping each element:\n\n";
while (!heap.empty()) {
std::cout << "----> " << heap.top() << std::endl;
heap.pop();
std::cout << "\n" << heap << std::endl;
}
std::cout << "## Adding all the items back in:\n" << std::endl;
for (const auto& food : foodList) {
std::cout << "<---- " << food << std::endl;
heap.push(food);
std::cout << "\n" << heap << std::endl;
}
// We can also use our heap to make a priority queue, using a pair
// where the first element is the priority and the second element is
// the value. We could just use std::tuple instead of Prioritized, but
// this is a bit more readable.
using PriorityFood = Prioritized<std::string>;
std::cout << "\n# Priority Queue Example\n" << std::endl;
auto priorities = {5, 10, 11, 1, 4, 8, 3}; // , 7, 2, 9};
std::vector<PriorityFood> pqFoods;
auto pIter = priorities.begin();
for (const auto& food : foodList) {
pqFoods.push_back({*pIter, food});
++pIter;
if (pIter == priorities.end()) {
break;
}
}
std::cout << "## Complete prority-queue tree (before heapify):\n\n";
Heap<PriorityFood>::printCompleteTree(std::cout, pqFoods);
std::cout << "\n## Priority queue (after heapify):\n\n";
Heap<PriorityFood> priorityQueue{pqFoods}; // Performs a heapify operation
std::cout << priorityQueue << std::endl;
std::cout << "## Repeatedly change priority of top element (+5):\n";
for (int i = 0; i < 12; ++i) {
auto top = priorityQueue.top();
std::cout << "\n----> " << top << std::endl;
top.priority += 5;
top.value += "!";
std::cout << "<---- " << top << std::endl;
priorityQueue.updateTop(top);
std::cout << "\n" << priorityQueue << std::endl;
}
return 0;
}
/*
* This code shows a simple implementation of a heap data structure, as
* a C++ class template. The heap is represented using a std::vector.
*
* Useful notes:
* - The heap is represented as a vector, with the root at index 0.
* - The left child of a node at index i is at index 2*i+1.
* - The right child of a node at index i is at index 2*i+2.
* - The parent of a node at index i is at index (i-1)/2.
* - The last node that has children is at index size/2 - 1.
*
* THe code is written for the C++17 standard.
*/
#ifndef HEAP_HPP_INCLUDED
#define HEAP_HPP_INCLUDED
#include <vector>
#include <algorithm>
#include <functional>
#include <utility>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <stdexcept>
#include <cstddef>
template <typename T, typename Compare = std::less<T>>
class Heap {
public:
/**
* \brief Constructs an empty heap.
* \param capacity The initial capacity of the heap's internal vector
* (optional). \param comp The comparison function (optional).
*/
Heap(size_t capacity = 1, Compare comp = Compare());
/**
* \brief Constructs a heap from a vector of items (heapiyfies the vector).
* \param items The vector of items to use to initialize the heap.
* \param comp The comparison function (optional).
*/
Heap(std::vector<T>& v, Compare comp = Compare());
/**
* \brief Copy constructor.
*/
Heap(const Heap& h) = default;
/**
* \brief Copy-assignment operator.
*/
Heap& operator=(const Heap& h) = default;
/**
* \brief Destructor.
*/
~Heap() = default;
/**
* \brief Pushes an item onto the heap.
* \param item The item to push onto the heap.
*/
void push(const T& x);
/**
* \brief Removes the top item from the heap.
*/
void pop();
/**
* \brief Returns the top item from the heap.
* \return The top item from the heap.
*/
const T& top() const;
/**
* \brief Updates the top item on the heap and restores the heap property.
*/
void updateTop(const T& x);
/**
* \brief Returns whether the heap is empty.
* \return Whether the heap is empty.
*/
bool empty() const;
/**
* \brief Returns the size of the heap.
* \return The number of items in the heap.
*/
size_t size() const;
/**
* \brief Prints out the heap.
* \param os The output stream to print to.
* \return The output stream.
* \note Calls printCompleteTree passing in the heap's internal vector.
*/
std::ostream& printToStream(std::ostream& os) const;
/**
* \brief Prints out a complete tree from a vector.
* \param os The output stream to print to.
* \param vec The vector to print.
* \return The output stream.
*/
static std::ostream& printCompleteTree(std::ostream& os,
const std::vector<T>& vec);
private:
std::vector<T> data_;
Compare comp_;
void siftUp(size_t i);
void siftDown(size_t i);
};
template <typename T, typename Cmp>
std::ostream& operator<<(std::ostream& os, const Heap<T, Cmp>& h);
#include "heap-private.hpp"
#endif
#ifndef HEAP_HPP_INCLUDED
#error Do not include heap-private.hpp directly
#include "heap.hpp" // Only to prevent VS Code from being confused
#endif
template <typename T, typename Cmp>
Heap<T, Cmp>::Heap(size_t capacity, Cmp comp) : data_{}, comp_{comp} {
data_.reserve(capacity);
// Note that we allow the user to provide a comparison function but it
// defaults to std::less<T>, a function object that compares two values
// of type T using the < operator. This means that the default heap is a
// min-heap, but the user can also create a max-heap by passing in a
// comparison function that reverses the order.
}
template <typename T, typename Cmp>
Heap<T, Cmp>::Heap(std::vector<T>& v, Cmp comp)
: data_{std::move(v)}, comp_{comp} {
// Note, it's beyond the scope of CS 70, but the use of std::move here
// causes the heap to steal the vector's data, rather than copying it.
// This is the heapify operation, which takes O(n) time.
size_t i = data_.size() / 2;
while (i > 0) {
siftDown(--i);
}
}
template <typename T, typename Cmp>
void Heap<T, Cmp>::push(const T& x) {
data_.push_back(x);
siftUp(data_.size() - 1);
}
template <typename T, typename Cmp>
void Heap<T, Cmp>::pop() {
if (data_.empty()) {
throw std::out_of_range("Heap is empty");
}
data_[0] = std::move(data_.back());
data_.pop_back();
siftDown(0);
}
template <typename T, typename Cmp>
const T& Heap<T, Cmp>::top() const {
if (data_.empty()) {
throw std::out_of_range("Heap is empty");
}
return data_[0];
}
template <typename T, typename Cmp>
void Heap<T, Cmp>::updateTop(const T& x) {
if (data_.empty()) {
throw std::out_of_range("Heap is empty");
}
data_[0] = x;
siftDown(0);
}
template <typename T, typename Cmp>
bool Heap<T, Cmp>::empty() const {
return data_.empty();
}
template <typename T, typename Cmp>
size_t Heap<T, Cmp>::size() const {
return data_.size();
}
template <typename T, typename Cmp>
void Heap<T, Cmp>::siftUp(size_t i) {
while (i > 0) {
size_t parent = (i - 1) / 2;
if (comp_(data_[i], data_[parent])) {
using std::swap;
swap(data_[i], data_[parent]);
i = parent;
} else {
break;
}
}
}
template <typename T, typename Cmp>
void Heap<T, Cmp>::siftDown(size_t i) {
size_t size = data_.size();
if (size < 2) {
return;
}
size_t lastParent = size / 2 - 1;
size_t last = size - 1;
while (i <= lastParent) {
size_t left = 2 * i + 1;
size_t right = 2 * i + 2;
size_t child = left;
if (right <= last && comp_(data_[right], data_[left])) {
child = right;
}
if (comp_(data_[child], data_[i])) {
using std::swap;
swap(data_[i], data_[child]);
i = child;
} else {
break;
}
}
}
/* -- You can safely ignore the code below this point -- */
template <typename T, typename Cmp>
std::ostream& Heap<T, Cmp>::printCompleteTree(std::ostream& os,
const std::vector<T>& vec) {
// We print out the heap in a pyramid shape, with the root at the top.
//
// Suppose each level will be printed in a field width of 5, with a
// space between each element, for a total of six characters per item.
// We want the tree to look like this:
// xxxxx
// xxxxx xxxxx
// xxxxx xxxxx xxxxx xxxxx
// xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx
//
// Notice that the last line is 47 characters wide (8*6-1). The line
// above it has 4 items rather than 8 and indents by 3 spaces and then
// separates the items as if there was one blank item between them.
// The line above that has 2 items and indents by 9 spaces and separates
// the items as if there were three blank items between them. The line
// above that has 1 item and indents by 21 spaces (if it wasn't the final
// line, be separating the items as if there were seven blank items
// between them).
//
// Let's extract the pattern from this. The number of items on the last
// line is k = 2^(totalLevels-1).
// The indent for the 1st line is 21 = 48/2 - 3 = k*6/2 - 3,
// and if there was an extra gap, it would be 7 * 6 = 42 = 1st indent * 2.
// The indent for the 2nd line is 9 = 48/4 - 3 = k*6/4 - 3,
// and the extra gap 3 * 6 = 18 = 2nd indent * 2.
// The indent for the 3rd line is 3 = 48/8 - 3 = k*6/8 - 3,
// and the extra gap 1 * 6 = 6 = 3rd indent * 2.
// The indent for the 4th line is 0 = 48/16 - 3 = k*6/16 - 3.
// But we don't actually want to hard-code the field width, so we'll
// go through all our items first and mesure them, by printing to a
// stringstream and then measuring the length of the string.
size_t maxItemWidth = 0;
for (const T& item : vec) {
std::stringstream ss;
ss << item;
maxItemWidth = std::max(maxItemWidth, ss.str().size());
}
// Round it to an odd number
maxItemWidth |= 1;
size_t width = maxItemWidth + 1;
// totalLevels is the height of the tree, which is log2(size) + 1.
size_t totalLevels = 0;
for (size_t i = vec.size(); i > 0; i >>= 1) {
++totalLevels;
}
size_t indent = (width * (1 << totalLevels)) / 2 - width / 2;
// ^-- This is actually the indent for a mythical level 0, which doesn't
// exist. We'll use it to compute the indent for the first real level.
size_t level = 0;
size_t levelSize = 1;
size_t levelCount = 0;
for (const T& item : vec) {
if (levelCount == 0) {
// We're at the start of a new level.
if (level != 0) {
// Not the first level, so print a newline
os << std::endl;
}
indent = (indent + width / 2) / 2 - width / 2;
// ^-- This is the formula for the indent for the next level,
// derived from the discussion above.
levelCount = levelSize;
levelSize *= 2;
++level;
// We need to print indent spaces before the first item on
// this line.
os << std::setw(indent) << "";
}
// We print each item in a field width of maxItemWidth, with one space
// and then any extra gap as per the discussion above. For maximum
// prettiness, we center the text in the field, by measuring how
// much space we need to pad it on either side.
std::stringstream ss;
ss << item;
size_t itemWidth = ss.str().size();
size_t pad = (maxItemWidth - itemWidth) / 2;
os << std::setw(maxItemWidth) << (ss.str() + std::string(pad, ' '));
--levelCount;
if (levelCount != 0) {
// We're not at the end of the line, so print the gap
os << std::setw(indent * 2 + 1) << "";
}
}
std::cout << std::endl;
return os;
}
template <typename T, typename Cmp>
std::ostream& Heap<T, Cmp>::printToStream(std::ostream& os) const {
return printCompleteTree(os, data_);
}
template <typename T, typename Cmp>
std::ostream& operator<<(std::ostream& os, const Heap<T, Cmp>& h) {
return h.printToStream(os);
}
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|