i'm working through Cormen et al., Intro to Algorithms, and on the heap chap. (ch. 6), i thought it would be a good exercise to convert the pseudo-code into an actual C++ class. while i try to stick as closely as possible to the book's methods, there are certainly a few different ways one could set this up (e.g., MaxHeap and MinHeap as just one class Heap, with a boolean constructor indicating max or min, but i thought that would lead to more trouble than just making separate classes, even though there's a lot of repetition of code, just changing < to >).
anyhow, i just wanted to hear opinions and critique of my MaxHeap class:
Code:
#ifndef HEAP_H
#define HEAP_H
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <iostream>
template<typename T>
class MaxHeap {
private:
std::vector<T> heap;
int parent(int i) {return (i - 1) / 2;} // returns index of parent (no bounds checking)
int left(int i) {return 2 * i + 1;} // index of left child (no bounds checking)
int right(int i) {return 2 * i + 2;} // index of right child (no bounds checking)
/**
under the assumption (!!) that the portions of heap rooted at left(i) and right(i) are max-heaps
makes the portion of heap rooted at i into a max heap
*/
void max_heapify(int i);
void build_max_heap();
/**
used for inserting new elements
allows key to float up through the heap as necessary
@param i
index at which heap will initially be overwritten with element key
@param key
value of element to insert at index i
the idea is that i will NOT be the final index of key
but key will be moved up appropriately when key >= heap.at(i)
*/
void heap_increase_key(int i, T key) throw(std::invalid_argument); // needed for max_heap_insert()
public:
// default constructor just uses vector<T> default constructor (heap is empty)
MaxHeap() {}
// constructor from vector
MaxHeap(std::vector<T> v);
// constructor from array
MaxHeap(T arr[], size_t size);
// accessor
const T at(int i);
void show();
MaxHeap<T>& operator=(const MaxHeap<T>&);
/**
note that to get a sorted copy of an arbitrary vector, this implementation requires 2 steps:
1) use your vector to contruct a heap
2) run the heap_sort() method
WARNING! this method clears also clears the contents of heap
heap will be empty after this method has run
I implemented it this way in order to optimize the class for sorting even large inputs
(other option would be making a copy of heap)
@return vector<T>
vector is a sorted version of heap
*/
std::vector<T> heap_sort();
T heap_maximum() throw(std::underflow_error); // Cormen et al., p. 163
T heap_extract_max() throw(std::underflow_error); // Cormen et al., p. 163
void max_heap_insert(const T key);
};
// constructor from vector
template<typename T>
MaxHeap<T>::MaxHeap(std::vector<T> v) {
heap = v;
build_max_heap();
}
// constructor from array
template<typename T>
MaxHeap<T>::MaxHeap(T arr[], size_t size) {
std::vector<T> v(arr, arr + size);
heap = v;
build_max_heap();
}
template<typename T>
void MaxHeap<T>::max_heapify(int i) {
int left = MaxHeap<T>::left(i), right = MaxHeap<T>::right(i), largest;
size_t heap_size = heap.size();
if (left < heap_size && heap.at(left) > heap.at(i)) largest = left;
else largest = i;
if (right < heap_size && heap.at(right) > heap.at(largest)) largest = right;
if (largest != i) {
std::swap(heap.at(i), heap.at(largest));
max_heapify(largest);
}
}
template<typename T>
void MaxHeap<T>::build_max_heap() {
size_t size = heap.size();
for (int i = size / 2 - 1; i >= 0; --i) {
max_heapify(i);
}
}
template<typename T>
const T MaxHeap<T>::at(int i) {
return heap.at(i); // exception will be thrown if i is out of range
}
template<typename T>
void MaxHeap<T>::show() {
size_t size = heap.size();
int i;
std::cout << "<";
if (size > 0) {
for (i = 0; i < size - 1; ++i) {
std::cout << heap.at(i) << ", ";
}
std::cout << heap.at(i);
}
std::cout << ">";
}
template<typename T>
MaxHeap<T>& MaxHeap<T>::operator=(const MaxHeap<T>& h) {
heap = h.heap;
return h;
}
template<typename T>
std::vector<T> MaxHeap<T>::heap_sort() {
std::vector<T> result;
size_t size = heap.size();
if (size > 0) {
for (int i = size - 1; i >= 0; --i) {
std::swap(heap.at(0), heap.at(i));
result.push_back(heap.back());
heap.pop_back();
max_heapify(0);
}
}
return result;
}
template<typename T>
T MaxHeap<T>::heap_maximum() throw(std::underflow_error) {
if (!heap.size()) throw std::underflow_error("Heap is empty!");
return heap.at(0);
}
template<typename T>
T MaxHeap<T>::heap_extract_max() throw(std::underflow_error) {
size_t size = heap.size();
if (!size()) throw std::underflow_error("Heap is empty!");
T result;
std::swap(heap.at(0), heap.at(size - 1));
result = heap.back();
heap.pop_back();
max_heapify(0);
return result;
}
template<typename T>
void MaxHeap<T>::heap_increase_key(int i, T key) throw(std::invalid_argument) {
if (key < heap.at(i)) throw std::invalid_argument("New key is smaller than current key!");
heap.at(i) = key;
while (i > 0 && heap.at(parent(i)) < heap.at(i)) {
std::swap(heap.at(i), heap.at(parent(i)));
i = parent(i);
}
}
template<typename T>
void MaxHeap<T>::max_heap_insert(T key) {
heap.push_back(key);
MaxHeap<T>::heap_increase_key(heap.size() - 1, key);
}
#endif