Maximum Heap Container
I implemented this max-heap to satisfy the C++ Container requirements. I am fairly confident I implemented bubble_up
, bubble_down
, and sort
correctly. It passes for small sets of numbers I give it. If you're wondering what bubble_down(iterator, iterator)
does, it does the bubble down action but ignores positions past last
(inclusive). In sort
, the vector becomes sorted from right to left, so as the root bubbles down it will not interact with the already sorted part. Also note that after sorting you will want to call build
to rebuild the heap.
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <utility>
#include <sstream>
#include <cmath>
template<typename Type>
class max_heap {
public:
using value_type = Type;
using reference = Type&;
using const_reference = const Type&;
using iterator = typename std::vector<Type>::iterator;
using const_iterator = typename std::vector<Type>::const_iterator;
using difference_type = typename std::vector<Type>::difference_type;
using size_type = typename std::vector<Type>::size_type;
max_heap() = default;
~max_heap() = default;
max_heap(iterator begin, iterator end);
max_heap(const max_heap<Type>& other);
max_heap(max_heap<Type>&& other);
iterator begin();
const_iterator begin() const;
const_iterator cbegin() const;
iterator end();
const_iterator end() const;
const_iterator cend() const;
reference operator=(max_heap<Type> other);
reference operator=(max_heap<Type>&& other);
bool operator==(const max_heap<Type>& other);
bool operator!=(const max_heap<Type>& other);
void swap(max_heap& other);
template<typename T>
friend void swap(max_heap<T>& lhs, max_heap<T>& rhs);
size_type size() const;
size_type max_size() const;
bool empty() const;
void sort();
void insert(value_type value);
void remove(iterator elem);
void remove_maximum();
reference maximum();
const_reference maximum() const;
// build tree in linear time
void build();
private:
iterator parent_of(iterator child);
iterator left_child_of(iterator parent);
iterator right_child_of(iterator parent);
void bubble_up(iterator elem);
void bubble_down(iterator elem);
void bubble_down(iterator elem, iterator last);
std::vector<int> rep;
};
template<typename Type>
max_heap<Type>::max_heap(iterator begin, iterator end)
: rep(begin, end) {
build();
}
template<typename Type>
max_heap<Type>::max_heap(const max_heap<Type>& other)
: rep(other.rep) { }
template<typename Type>
max_heap<Type>::max_heap(max_heap<Type>&& other) {
std::swap(rep, other.rep);
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::begin() { return rep.begin(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::begin() const { return rep.begin(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::cbegin() const { return rep.begin(); }
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::end() { return rep.end(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::end() const { return rep.end(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::cend() const { return rep.end(); }
template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::operator=(max_heap<Type> other) {
// copy-swap
std::swap(rep, other.rep);
return *this;
}
template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::operator=(max_heap<Type>&& other) {
// copy-swap
std::swap(rep, other.rep);
return *this;
}
template<typename Type>
bool max_heap<Type>::operator==(const max_heap<Type>& other) {
return std::equal(begin(), end(), other.begin(), other.end());
}
template<typename Type>
bool max_heap<Type>::operator!=(const max_heap<Type>& other) {
return !operator==(other);
}
template<typename Type>
void max_heap<Type>::swap(max_heap<Type>& other) {
std::swap(rep, other.rep);
}
template<typename Type>
void swap(max_heap<Type>& lhs, max_heap<Type> rhs) {
lhs.swap(rhs);
}
template<typename Type>
typename max_heap<Type>::size_type
max_heap<Type>::size() const { return rep.size(); }
template<typename Type>
typename max_heap<Type>::size_type
max_heap<Type>::max_size() const { return rep.max_size(); }
template<typename Type>
bool max_heap<Type>::empty() const { return rep.empty(); }
template<typename Type>
void max_heap<Type>::build() {
// skip leaf nodes
const auto n = begin() + std::ceil(size() / 2);
for (auto i = n; i >= begin(); --i)
bubble_down(i);
}
template<typename Type>
void max_heap<Type>::sort() {
auto iter = end() - 1;
while (iter >= begin()) {
std::swap(*begin(), *iter);
// bubble root down but ignore elements past iter
bubble_down(begin(), iter);
--iter;
}
}
template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::maximum() { return *begin(); }
template<typename Type>
typename max_heap<Type>::const_reference
max_heap<Type>::maximum() const { return *begin(); }
template<typename Type>
void max_heap<Type>::remove(iterator elem) {
std::swap(*elem, *(end() - 1));
rep.resize(size() - 1);
if (size() > 0)
bubble_down(begin());
}
template<typename Type>
void max_heap<Type>::remove_maximum() {
remove(begin());
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::parent_of(iterator child) {
// parent = floor((i - 1) / 2)
const auto idx = std::distance(begin(), child);
return begin() + (idx - 1) / 2;
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::left_child_of(iterator parent) {
// left_child = 2i + 1
const auto idx = std::distance(begin(), parent);
return begin() + (2 * idx) + 1;
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::right_child_of(iterator parent) {
// right_child = 2i + 2
const auto idx = std::distance(begin(), parent);
return begin() + (2 * idx) + 2;
}
template<typename Type>
void max_heap<Type>::bubble_up(iterator elem) {
auto child = elem;
auto parent = parent_of(child);
// bubble up
while (child != parent && *child > *parent) {
std::swap(*child, *parent);
child = parent;
parent = parent_of(parent);
}
}
template<typename Type>
void max_heap<Type>::bubble_down(iterator elem) {
bubble_down(elem, end());
}
template<typename Type>
void max_heap<Type>::bubble_down(iterator elem, iterator last) {
auto parent = elem;
auto left_child = left_child_of(parent);
auto right_child = right_child_of(parent);
// stop at last
while (left_child < last || right_child < last) {
// find maximum of parent, left_child, right_child
auto max = parent;
if (left_child < last)
if (*max < *left_child)
max = left_child;
if (right_child < last)
if (*max < *right_child)
max = right_child;
// max_heap property fixed
if (parent == max) break;
// swap with the greater child
std::swap(*parent, *max);
parent = max;
left_child = left_child_of(parent);
right_child = right_child_of(parent);
}
}
template<typename Type>
void max_heap<Type>::insert(value_type value) {
rep.push_back(value);
bubble_up(end() - 1);
}
template<typename Type>
std::ostream& operator<<(std::ostream& out, const max_heap<Type>& max_heap) {
// output contents of max_heap
if (max_heap.size() > 0) {
std::cout << *max_heap.begin();
for (auto i = max_heap.begin() + 1; i < max_heap.end(); ++i)
std::cout << ' ' << *i;
}
return out;
}
int main() {
std::string line;
// get set of integers from stdin
do {
std::cout << "insert set of integers: ";
std::getline(std::cin, line);
} while (line == "");
// parse stdin input into vector<int>
std::stringstream stream(line);
std::vector<int> arr;
while (std::getline(stream, line, ' ')) {
try {
const int n = std::stoi(line);
arr.push_back(n);
} catch (...) {
// ignore for now
continue;
}
}
// linear time to build max_heap
max_heap<int> h(arr.begin(), arr.end());
std::cout << "h before: " << h << 'n';
h.sort();
std::cout << "h sorted: " << h << 'n';
h.build();
h.insert(22);
std::cout << "h inserted: " << h << 'n';
}
EDIT: I also realized I can std::move
the value into the vector in insert
.
EDIT2: I realized that inside of build
it should be const auto n = begin() + (size() / 2) - 1;
. What is above is not strictly wrong but it may do one more bubble_down
than is necessary.
c++ reinventing-the-wheel heap heap-sort
add a comment |
I implemented this max-heap to satisfy the C++ Container requirements. I am fairly confident I implemented bubble_up
, bubble_down
, and sort
correctly. It passes for small sets of numbers I give it. If you're wondering what bubble_down(iterator, iterator)
does, it does the bubble down action but ignores positions past last
(inclusive). In sort
, the vector becomes sorted from right to left, so as the root bubbles down it will not interact with the already sorted part. Also note that after sorting you will want to call build
to rebuild the heap.
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <utility>
#include <sstream>
#include <cmath>
template<typename Type>
class max_heap {
public:
using value_type = Type;
using reference = Type&;
using const_reference = const Type&;
using iterator = typename std::vector<Type>::iterator;
using const_iterator = typename std::vector<Type>::const_iterator;
using difference_type = typename std::vector<Type>::difference_type;
using size_type = typename std::vector<Type>::size_type;
max_heap() = default;
~max_heap() = default;
max_heap(iterator begin, iterator end);
max_heap(const max_heap<Type>& other);
max_heap(max_heap<Type>&& other);
iterator begin();
const_iterator begin() const;
const_iterator cbegin() const;
iterator end();
const_iterator end() const;
const_iterator cend() const;
reference operator=(max_heap<Type> other);
reference operator=(max_heap<Type>&& other);
bool operator==(const max_heap<Type>& other);
bool operator!=(const max_heap<Type>& other);
void swap(max_heap& other);
template<typename T>
friend void swap(max_heap<T>& lhs, max_heap<T>& rhs);
size_type size() const;
size_type max_size() const;
bool empty() const;
void sort();
void insert(value_type value);
void remove(iterator elem);
void remove_maximum();
reference maximum();
const_reference maximum() const;
// build tree in linear time
void build();
private:
iterator parent_of(iterator child);
iterator left_child_of(iterator parent);
iterator right_child_of(iterator parent);
void bubble_up(iterator elem);
void bubble_down(iterator elem);
void bubble_down(iterator elem, iterator last);
std::vector<int> rep;
};
template<typename Type>
max_heap<Type>::max_heap(iterator begin, iterator end)
: rep(begin, end) {
build();
}
template<typename Type>
max_heap<Type>::max_heap(const max_heap<Type>& other)
: rep(other.rep) { }
template<typename Type>
max_heap<Type>::max_heap(max_heap<Type>&& other) {
std::swap(rep, other.rep);
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::begin() { return rep.begin(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::begin() const { return rep.begin(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::cbegin() const { return rep.begin(); }
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::end() { return rep.end(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::end() const { return rep.end(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::cend() const { return rep.end(); }
template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::operator=(max_heap<Type> other) {
// copy-swap
std::swap(rep, other.rep);
return *this;
}
template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::operator=(max_heap<Type>&& other) {
// copy-swap
std::swap(rep, other.rep);
return *this;
}
template<typename Type>
bool max_heap<Type>::operator==(const max_heap<Type>& other) {
return std::equal(begin(), end(), other.begin(), other.end());
}
template<typename Type>
bool max_heap<Type>::operator!=(const max_heap<Type>& other) {
return !operator==(other);
}
template<typename Type>
void max_heap<Type>::swap(max_heap<Type>& other) {
std::swap(rep, other.rep);
}
template<typename Type>
void swap(max_heap<Type>& lhs, max_heap<Type> rhs) {
lhs.swap(rhs);
}
template<typename Type>
typename max_heap<Type>::size_type
max_heap<Type>::size() const { return rep.size(); }
template<typename Type>
typename max_heap<Type>::size_type
max_heap<Type>::max_size() const { return rep.max_size(); }
template<typename Type>
bool max_heap<Type>::empty() const { return rep.empty(); }
template<typename Type>
void max_heap<Type>::build() {
// skip leaf nodes
const auto n = begin() + std::ceil(size() / 2);
for (auto i = n; i >= begin(); --i)
bubble_down(i);
}
template<typename Type>
void max_heap<Type>::sort() {
auto iter = end() - 1;
while (iter >= begin()) {
std::swap(*begin(), *iter);
// bubble root down but ignore elements past iter
bubble_down(begin(), iter);
--iter;
}
}
template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::maximum() { return *begin(); }
template<typename Type>
typename max_heap<Type>::const_reference
max_heap<Type>::maximum() const { return *begin(); }
template<typename Type>
void max_heap<Type>::remove(iterator elem) {
std::swap(*elem, *(end() - 1));
rep.resize(size() - 1);
if (size() > 0)
bubble_down(begin());
}
template<typename Type>
void max_heap<Type>::remove_maximum() {
remove(begin());
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::parent_of(iterator child) {
// parent = floor((i - 1) / 2)
const auto idx = std::distance(begin(), child);
return begin() + (idx - 1) / 2;
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::left_child_of(iterator parent) {
// left_child = 2i + 1
const auto idx = std::distance(begin(), parent);
return begin() + (2 * idx) + 1;
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::right_child_of(iterator parent) {
// right_child = 2i + 2
const auto idx = std::distance(begin(), parent);
return begin() + (2 * idx) + 2;
}
template<typename Type>
void max_heap<Type>::bubble_up(iterator elem) {
auto child = elem;
auto parent = parent_of(child);
// bubble up
while (child != parent && *child > *parent) {
std::swap(*child, *parent);
child = parent;
parent = parent_of(parent);
}
}
template<typename Type>
void max_heap<Type>::bubble_down(iterator elem) {
bubble_down(elem, end());
}
template<typename Type>
void max_heap<Type>::bubble_down(iterator elem, iterator last) {
auto parent = elem;
auto left_child = left_child_of(parent);
auto right_child = right_child_of(parent);
// stop at last
while (left_child < last || right_child < last) {
// find maximum of parent, left_child, right_child
auto max = parent;
if (left_child < last)
if (*max < *left_child)
max = left_child;
if (right_child < last)
if (*max < *right_child)
max = right_child;
// max_heap property fixed
if (parent == max) break;
// swap with the greater child
std::swap(*parent, *max);
parent = max;
left_child = left_child_of(parent);
right_child = right_child_of(parent);
}
}
template<typename Type>
void max_heap<Type>::insert(value_type value) {
rep.push_back(value);
bubble_up(end() - 1);
}
template<typename Type>
std::ostream& operator<<(std::ostream& out, const max_heap<Type>& max_heap) {
// output contents of max_heap
if (max_heap.size() > 0) {
std::cout << *max_heap.begin();
for (auto i = max_heap.begin() + 1; i < max_heap.end(); ++i)
std::cout << ' ' << *i;
}
return out;
}
int main() {
std::string line;
// get set of integers from stdin
do {
std::cout << "insert set of integers: ";
std::getline(std::cin, line);
} while (line == "");
// parse stdin input into vector<int>
std::stringstream stream(line);
std::vector<int> arr;
while (std::getline(stream, line, ' ')) {
try {
const int n = std::stoi(line);
arr.push_back(n);
} catch (...) {
// ignore for now
continue;
}
}
// linear time to build max_heap
max_heap<int> h(arr.begin(), arr.end());
std::cout << "h before: " << h << 'n';
h.sort();
std::cout << "h sorted: " << h << 'n';
h.build();
h.insert(22);
std::cout << "h inserted: " << h << 'n';
}
EDIT: I also realized I can std::move
the value into the vector in insert
.
EDIT2: I realized that inside of build
it should be const auto n = begin() + (size() / 2) - 1;
. What is above is not strictly wrong but it may do one more bubble_down
than is necessary.
c++ reinventing-the-wheel heap heap-sort
add a comment |
I implemented this max-heap to satisfy the C++ Container requirements. I am fairly confident I implemented bubble_up
, bubble_down
, and sort
correctly. It passes for small sets of numbers I give it. If you're wondering what bubble_down(iterator, iterator)
does, it does the bubble down action but ignores positions past last
(inclusive). In sort
, the vector becomes sorted from right to left, so as the root bubbles down it will not interact with the already sorted part. Also note that after sorting you will want to call build
to rebuild the heap.
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <utility>
#include <sstream>
#include <cmath>
template<typename Type>
class max_heap {
public:
using value_type = Type;
using reference = Type&;
using const_reference = const Type&;
using iterator = typename std::vector<Type>::iterator;
using const_iterator = typename std::vector<Type>::const_iterator;
using difference_type = typename std::vector<Type>::difference_type;
using size_type = typename std::vector<Type>::size_type;
max_heap() = default;
~max_heap() = default;
max_heap(iterator begin, iterator end);
max_heap(const max_heap<Type>& other);
max_heap(max_heap<Type>&& other);
iterator begin();
const_iterator begin() const;
const_iterator cbegin() const;
iterator end();
const_iterator end() const;
const_iterator cend() const;
reference operator=(max_heap<Type> other);
reference operator=(max_heap<Type>&& other);
bool operator==(const max_heap<Type>& other);
bool operator!=(const max_heap<Type>& other);
void swap(max_heap& other);
template<typename T>
friend void swap(max_heap<T>& lhs, max_heap<T>& rhs);
size_type size() const;
size_type max_size() const;
bool empty() const;
void sort();
void insert(value_type value);
void remove(iterator elem);
void remove_maximum();
reference maximum();
const_reference maximum() const;
// build tree in linear time
void build();
private:
iterator parent_of(iterator child);
iterator left_child_of(iterator parent);
iterator right_child_of(iterator parent);
void bubble_up(iterator elem);
void bubble_down(iterator elem);
void bubble_down(iterator elem, iterator last);
std::vector<int> rep;
};
template<typename Type>
max_heap<Type>::max_heap(iterator begin, iterator end)
: rep(begin, end) {
build();
}
template<typename Type>
max_heap<Type>::max_heap(const max_heap<Type>& other)
: rep(other.rep) { }
template<typename Type>
max_heap<Type>::max_heap(max_heap<Type>&& other) {
std::swap(rep, other.rep);
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::begin() { return rep.begin(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::begin() const { return rep.begin(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::cbegin() const { return rep.begin(); }
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::end() { return rep.end(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::end() const { return rep.end(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::cend() const { return rep.end(); }
template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::operator=(max_heap<Type> other) {
// copy-swap
std::swap(rep, other.rep);
return *this;
}
template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::operator=(max_heap<Type>&& other) {
// copy-swap
std::swap(rep, other.rep);
return *this;
}
template<typename Type>
bool max_heap<Type>::operator==(const max_heap<Type>& other) {
return std::equal(begin(), end(), other.begin(), other.end());
}
template<typename Type>
bool max_heap<Type>::operator!=(const max_heap<Type>& other) {
return !operator==(other);
}
template<typename Type>
void max_heap<Type>::swap(max_heap<Type>& other) {
std::swap(rep, other.rep);
}
template<typename Type>
void swap(max_heap<Type>& lhs, max_heap<Type> rhs) {
lhs.swap(rhs);
}
template<typename Type>
typename max_heap<Type>::size_type
max_heap<Type>::size() const { return rep.size(); }
template<typename Type>
typename max_heap<Type>::size_type
max_heap<Type>::max_size() const { return rep.max_size(); }
template<typename Type>
bool max_heap<Type>::empty() const { return rep.empty(); }
template<typename Type>
void max_heap<Type>::build() {
// skip leaf nodes
const auto n = begin() + std::ceil(size() / 2);
for (auto i = n; i >= begin(); --i)
bubble_down(i);
}
template<typename Type>
void max_heap<Type>::sort() {
auto iter = end() - 1;
while (iter >= begin()) {
std::swap(*begin(), *iter);
// bubble root down but ignore elements past iter
bubble_down(begin(), iter);
--iter;
}
}
template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::maximum() { return *begin(); }
template<typename Type>
typename max_heap<Type>::const_reference
max_heap<Type>::maximum() const { return *begin(); }
template<typename Type>
void max_heap<Type>::remove(iterator elem) {
std::swap(*elem, *(end() - 1));
rep.resize(size() - 1);
if (size() > 0)
bubble_down(begin());
}
template<typename Type>
void max_heap<Type>::remove_maximum() {
remove(begin());
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::parent_of(iterator child) {
// parent = floor((i - 1) / 2)
const auto idx = std::distance(begin(), child);
return begin() + (idx - 1) / 2;
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::left_child_of(iterator parent) {
// left_child = 2i + 1
const auto idx = std::distance(begin(), parent);
return begin() + (2 * idx) + 1;
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::right_child_of(iterator parent) {
// right_child = 2i + 2
const auto idx = std::distance(begin(), parent);
return begin() + (2 * idx) + 2;
}
template<typename Type>
void max_heap<Type>::bubble_up(iterator elem) {
auto child = elem;
auto parent = parent_of(child);
// bubble up
while (child != parent && *child > *parent) {
std::swap(*child, *parent);
child = parent;
parent = parent_of(parent);
}
}
template<typename Type>
void max_heap<Type>::bubble_down(iterator elem) {
bubble_down(elem, end());
}
template<typename Type>
void max_heap<Type>::bubble_down(iterator elem, iterator last) {
auto parent = elem;
auto left_child = left_child_of(parent);
auto right_child = right_child_of(parent);
// stop at last
while (left_child < last || right_child < last) {
// find maximum of parent, left_child, right_child
auto max = parent;
if (left_child < last)
if (*max < *left_child)
max = left_child;
if (right_child < last)
if (*max < *right_child)
max = right_child;
// max_heap property fixed
if (parent == max) break;
// swap with the greater child
std::swap(*parent, *max);
parent = max;
left_child = left_child_of(parent);
right_child = right_child_of(parent);
}
}
template<typename Type>
void max_heap<Type>::insert(value_type value) {
rep.push_back(value);
bubble_up(end() - 1);
}
template<typename Type>
std::ostream& operator<<(std::ostream& out, const max_heap<Type>& max_heap) {
// output contents of max_heap
if (max_heap.size() > 0) {
std::cout << *max_heap.begin();
for (auto i = max_heap.begin() + 1; i < max_heap.end(); ++i)
std::cout << ' ' << *i;
}
return out;
}
int main() {
std::string line;
// get set of integers from stdin
do {
std::cout << "insert set of integers: ";
std::getline(std::cin, line);
} while (line == "");
// parse stdin input into vector<int>
std::stringstream stream(line);
std::vector<int> arr;
while (std::getline(stream, line, ' ')) {
try {
const int n = std::stoi(line);
arr.push_back(n);
} catch (...) {
// ignore for now
continue;
}
}
// linear time to build max_heap
max_heap<int> h(arr.begin(), arr.end());
std::cout << "h before: " << h << 'n';
h.sort();
std::cout << "h sorted: " << h << 'n';
h.build();
h.insert(22);
std::cout << "h inserted: " << h << 'n';
}
EDIT: I also realized I can std::move
the value into the vector in insert
.
EDIT2: I realized that inside of build
it should be const auto n = begin() + (size() / 2) - 1;
. What is above is not strictly wrong but it may do one more bubble_down
than is necessary.
c++ reinventing-the-wheel heap heap-sort
I implemented this max-heap to satisfy the C++ Container requirements. I am fairly confident I implemented bubble_up
, bubble_down
, and sort
correctly. It passes for small sets of numbers I give it. If you're wondering what bubble_down(iterator, iterator)
does, it does the bubble down action but ignores positions past last
(inclusive). In sort
, the vector becomes sorted from right to left, so as the root bubbles down it will not interact with the already sorted part. Also note that after sorting you will want to call build
to rebuild the heap.
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <utility>
#include <sstream>
#include <cmath>
template<typename Type>
class max_heap {
public:
using value_type = Type;
using reference = Type&;
using const_reference = const Type&;
using iterator = typename std::vector<Type>::iterator;
using const_iterator = typename std::vector<Type>::const_iterator;
using difference_type = typename std::vector<Type>::difference_type;
using size_type = typename std::vector<Type>::size_type;
max_heap() = default;
~max_heap() = default;
max_heap(iterator begin, iterator end);
max_heap(const max_heap<Type>& other);
max_heap(max_heap<Type>&& other);
iterator begin();
const_iterator begin() const;
const_iterator cbegin() const;
iterator end();
const_iterator end() const;
const_iterator cend() const;
reference operator=(max_heap<Type> other);
reference operator=(max_heap<Type>&& other);
bool operator==(const max_heap<Type>& other);
bool operator!=(const max_heap<Type>& other);
void swap(max_heap& other);
template<typename T>
friend void swap(max_heap<T>& lhs, max_heap<T>& rhs);
size_type size() const;
size_type max_size() const;
bool empty() const;
void sort();
void insert(value_type value);
void remove(iterator elem);
void remove_maximum();
reference maximum();
const_reference maximum() const;
// build tree in linear time
void build();
private:
iterator parent_of(iterator child);
iterator left_child_of(iterator parent);
iterator right_child_of(iterator parent);
void bubble_up(iterator elem);
void bubble_down(iterator elem);
void bubble_down(iterator elem, iterator last);
std::vector<int> rep;
};
template<typename Type>
max_heap<Type>::max_heap(iterator begin, iterator end)
: rep(begin, end) {
build();
}
template<typename Type>
max_heap<Type>::max_heap(const max_heap<Type>& other)
: rep(other.rep) { }
template<typename Type>
max_heap<Type>::max_heap(max_heap<Type>&& other) {
std::swap(rep, other.rep);
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::begin() { return rep.begin(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::begin() const { return rep.begin(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::cbegin() const { return rep.begin(); }
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::end() { return rep.end(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::end() const { return rep.end(); }
template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::cend() const { return rep.end(); }
template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::operator=(max_heap<Type> other) {
// copy-swap
std::swap(rep, other.rep);
return *this;
}
template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::operator=(max_heap<Type>&& other) {
// copy-swap
std::swap(rep, other.rep);
return *this;
}
template<typename Type>
bool max_heap<Type>::operator==(const max_heap<Type>& other) {
return std::equal(begin(), end(), other.begin(), other.end());
}
template<typename Type>
bool max_heap<Type>::operator!=(const max_heap<Type>& other) {
return !operator==(other);
}
template<typename Type>
void max_heap<Type>::swap(max_heap<Type>& other) {
std::swap(rep, other.rep);
}
template<typename Type>
void swap(max_heap<Type>& lhs, max_heap<Type> rhs) {
lhs.swap(rhs);
}
template<typename Type>
typename max_heap<Type>::size_type
max_heap<Type>::size() const { return rep.size(); }
template<typename Type>
typename max_heap<Type>::size_type
max_heap<Type>::max_size() const { return rep.max_size(); }
template<typename Type>
bool max_heap<Type>::empty() const { return rep.empty(); }
template<typename Type>
void max_heap<Type>::build() {
// skip leaf nodes
const auto n = begin() + std::ceil(size() / 2);
for (auto i = n; i >= begin(); --i)
bubble_down(i);
}
template<typename Type>
void max_heap<Type>::sort() {
auto iter = end() - 1;
while (iter >= begin()) {
std::swap(*begin(), *iter);
// bubble root down but ignore elements past iter
bubble_down(begin(), iter);
--iter;
}
}
template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::maximum() { return *begin(); }
template<typename Type>
typename max_heap<Type>::const_reference
max_heap<Type>::maximum() const { return *begin(); }
template<typename Type>
void max_heap<Type>::remove(iterator elem) {
std::swap(*elem, *(end() - 1));
rep.resize(size() - 1);
if (size() > 0)
bubble_down(begin());
}
template<typename Type>
void max_heap<Type>::remove_maximum() {
remove(begin());
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::parent_of(iterator child) {
// parent = floor((i - 1) / 2)
const auto idx = std::distance(begin(), child);
return begin() + (idx - 1) / 2;
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::left_child_of(iterator parent) {
// left_child = 2i + 1
const auto idx = std::distance(begin(), parent);
return begin() + (2 * idx) + 1;
}
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::right_child_of(iterator parent) {
// right_child = 2i + 2
const auto idx = std::distance(begin(), parent);
return begin() + (2 * idx) + 2;
}
template<typename Type>
void max_heap<Type>::bubble_up(iterator elem) {
auto child = elem;
auto parent = parent_of(child);
// bubble up
while (child != parent && *child > *parent) {
std::swap(*child, *parent);
child = parent;
parent = parent_of(parent);
}
}
template<typename Type>
void max_heap<Type>::bubble_down(iterator elem) {
bubble_down(elem, end());
}
template<typename Type>
void max_heap<Type>::bubble_down(iterator elem, iterator last) {
auto parent = elem;
auto left_child = left_child_of(parent);
auto right_child = right_child_of(parent);
// stop at last
while (left_child < last || right_child < last) {
// find maximum of parent, left_child, right_child
auto max = parent;
if (left_child < last)
if (*max < *left_child)
max = left_child;
if (right_child < last)
if (*max < *right_child)
max = right_child;
// max_heap property fixed
if (parent == max) break;
// swap with the greater child
std::swap(*parent, *max);
parent = max;
left_child = left_child_of(parent);
right_child = right_child_of(parent);
}
}
template<typename Type>
void max_heap<Type>::insert(value_type value) {
rep.push_back(value);
bubble_up(end() - 1);
}
template<typename Type>
std::ostream& operator<<(std::ostream& out, const max_heap<Type>& max_heap) {
// output contents of max_heap
if (max_heap.size() > 0) {
std::cout << *max_heap.begin();
for (auto i = max_heap.begin() + 1; i < max_heap.end(); ++i)
std::cout << ' ' << *i;
}
return out;
}
int main() {
std::string line;
// get set of integers from stdin
do {
std::cout << "insert set of integers: ";
std::getline(std::cin, line);
} while (line == "");
// parse stdin input into vector<int>
std::stringstream stream(line);
std::vector<int> arr;
while (std::getline(stream, line, ' ')) {
try {
const int n = std::stoi(line);
arr.push_back(n);
} catch (...) {
// ignore for now
continue;
}
}
// linear time to build max_heap
max_heap<int> h(arr.begin(), arr.end());
std::cout << "h before: " << h << 'n';
h.sort();
std::cout << "h sorted: " << h << 'n';
h.build();
h.insert(22);
std::cout << "h inserted: " << h << 'n';
}
EDIT: I also realized I can std::move
the value into the vector in insert
.
EDIT2: I realized that inside of build
it should be const auto n = begin() + (size() / 2) - 1;
. What is above is not strictly wrong but it may do one more bubble_down
than is necessary.
c++ reinventing-the-wheel heap heap-sort
c++ reinventing-the-wheel heap heap-sort
edited Nov 14 '18 at 20:49
asked Nov 14 '18 at 4:15
Brady Dean
30417
30417
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
You have a container that can store anything
template<typename Type>
class max_heap
but your underlying storage is this
std::vector<int> rep;
I'm somewhat shocked that you didn't notice this. Did you only test it on integers?
You define everything out-of-line but this makes the overall implementation quite a bit larger than it needs to be, while also making the code a little less pleasant to read. If you want to add or remove a function, you have to do it twice.
In the class, you have a forward declaration
iterator begin();
...then you have the implementation later.
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::begin() { return rep.begin(); }
You could just do this
iterator begin() { return rep.begin(); }
In the sort
function, you have this
std::swap(*begin(), *iter);
When swapping two objects and you don't know what their type is, you should allow ADL to find custom swap functions. This pattern is very common in generic code. The standard library does this as well.
using std::swap;
swap(*begin(), *iter);
If you have a class with its own swap function like this
namespace my {
class swappable_thing {};
void swap(swappable_thing &, swappable_thing &) {
std::cout << "Custom swapn";
}
}
This following code does not call the custom swap function
my::swappable_thing a, b;
std::swap(a, b);
but this does
my::swappable_thing a, b;
using std::swap;
swap(a, b);
C++ has algorithms devoted to dealing with heaps. You're not using them. If there is a standard algorithm that does what you need it to do, use it. Your code becomes much simpler when you use standard algorithms.
I wrote the code using just ints then made it generic. I didn’t catch the vector<int> because I only tested with ints.
– Brady Dean
Nov 14 '18 at 12:03
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207624%2fmaximum-heap-container%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
You have a container that can store anything
template<typename Type>
class max_heap
but your underlying storage is this
std::vector<int> rep;
I'm somewhat shocked that you didn't notice this. Did you only test it on integers?
You define everything out-of-line but this makes the overall implementation quite a bit larger than it needs to be, while also making the code a little less pleasant to read. If you want to add or remove a function, you have to do it twice.
In the class, you have a forward declaration
iterator begin();
...then you have the implementation later.
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::begin() { return rep.begin(); }
You could just do this
iterator begin() { return rep.begin(); }
In the sort
function, you have this
std::swap(*begin(), *iter);
When swapping two objects and you don't know what their type is, you should allow ADL to find custom swap functions. This pattern is very common in generic code. The standard library does this as well.
using std::swap;
swap(*begin(), *iter);
If you have a class with its own swap function like this
namespace my {
class swappable_thing {};
void swap(swappable_thing &, swappable_thing &) {
std::cout << "Custom swapn";
}
}
This following code does not call the custom swap function
my::swappable_thing a, b;
std::swap(a, b);
but this does
my::swappable_thing a, b;
using std::swap;
swap(a, b);
C++ has algorithms devoted to dealing with heaps. You're not using them. If there is a standard algorithm that does what you need it to do, use it. Your code becomes much simpler when you use standard algorithms.
I wrote the code using just ints then made it generic. I didn’t catch the vector<int> because I only tested with ints.
– Brady Dean
Nov 14 '18 at 12:03
add a comment |
You have a container that can store anything
template<typename Type>
class max_heap
but your underlying storage is this
std::vector<int> rep;
I'm somewhat shocked that you didn't notice this. Did you only test it on integers?
You define everything out-of-line but this makes the overall implementation quite a bit larger than it needs to be, while also making the code a little less pleasant to read. If you want to add or remove a function, you have to do it twice.
In the class, you have a forward declaration
iterator begin();
...then you have the implementation later.
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::begin() { return rep.begin(); }
You could just do this
iterator begin() { return rep.begin(); }
In the sort
function, you have this
std::swap(*begin(), *iter);
When swapping two objects and you don't know what their type is, you should allow ADL to find custom swap functions. This pattern is very common in generic code. The standard library does this as well.
using std::swap;
swap(*begin(), *iter);
If you have a class with its own swap function like this
namespace my {
class swappable_thing {};
void swap(swappable_thing &, swappable_thing &) {
std::cout << "Custom swapn";
}
}
This following code does not call the custom swap function
my::swappable_thing a, b;
std::swap(a, b);
but this does
my::swappable_thing a, b;
using std::swap;
swap(a, b);
C++ has algorithms devoted to dealing with heaps. You're not using them. If there is a standard algorithm that does what you need it to do, use it. Your code becomes much simpler when you use standard algorithms.
I wrote the code using just ints then made it generic. I didn’t catch the vector<int> because I only tested with ints.
– Brady Dean
Nov 14 '18 at 12:03
add a comment |
You have a container that can store anything
template<typename Type>
class max_heap
but your underlying storage is this
std::vector<int> rep;
I'm somewhat shocked that you didn't notice this. Did you only test it on integers?
You define everything out-of-line but this makes the overall implementation quite a bit larger than it needs to be, while also making the code a little less pleasant to read. If you want to add or remove a function, you have to do it twice.
In the class, you have a forward declaration
iterator begin();
...then you have the implementation later.
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::begin() { return rep.begin(); }
You could just do this
iterator begin() { return rep.begin(); }
In the sort
function, you have this
std::swap(*begin(), *iter);
When swapping two objects and you don't know what their type is, you should allow ADL to find custom swap functions. This pattern is very common in generic code. The standard library does this as well.
using std::swap;
swap(*begin(), *iter);
If you have a class with its own swap function like this
namespace my {
class swappable_thing {};
void swap(swappable_thing &, swappable_thing &) {
std::cout << "Custom swapn";
}
}
This following code does not call the custom swap function
my::swappable_thing a, b;
std::swap(a, b);
but this does
my::swappable_thing a, b;
using std::swap;
swap(a, b);
C++ has algorithms devoted to dealing with heaps. You're not using them. If there is a standard algorithm that does what you need it to do, use it. Your code becomes much simpler when you use standard algorithms.
You have a container that can store anything
template<typename Type>
class max_heap
but your underlying storage is this
std::vector<int> rep;
I'm somewhat shocked that you didn't notice this. Did you only test it on integers?
You define everything out-of-line but this makes the overall implementation quite a bit larger than it needs to be, while also making the code a little less pleasant to read. If you want to add or remove a function, you have to do it twice.
In the class, you have a forward declaration
iterator begin();
...then you have the implementation later.
template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::begin() { return rep.begin(); }
You could just do this
iterator begin() { return rep.begin(); }
In the sort
function, you have this
std::swap(*begin(), *iter);
When swapping two objects and you don't know what their type is, you should allow ADL to find custom swap functions. This pattern is very common in generic code. The standard library does this as well.
using std::swap;
swap(*begin(), *iter);
If you have a class with its own swap function like this
namespace my {
class swappable_thing {};
void swap(swappable_thing &, swappable_thing &) {
std::cout << "Custom swapn";
}
}
This following code does not call the custom swap function
my::swappable_thing a, b;
std::swap(a, b);
but this does
my::swappable_thing a, b;
using std::swap;
swap(a, b);
C++ has algorithms devoted to dealing with heaps. You're not using them. If there is a standard algorithm that does what you need it to do, use it. Your code becomes much simpler when you use standard algorithms.
answered Nov 14 '18 at 6:20
Sneaky Turtle
763
763
I wrote the code using just ints then made it generic. I didn’t catch the vector<int> because I only tested with ints.
– Brady Dean
Nov 14 '18 at 12:03
add a comment |
I wrote the code using just ints then made it generic. I didn’t catch the vector<int> because I only tested with ints.
– Brady Dean
Nov 14 '18 at 12:03
I wrote the code using just ints then made it generic. I didn’t catch the vector<int> because I only tested with ints.
– Brady Dean
Nov 14 '18 at 12:03
I wrote the code using just ints then made it generic. I didn’t catch the vector<int> because I only tested with ints.
– Brady Dean
Nov 14 '18 at 12:03
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207624%2fmaximum-heap-container%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown