MaxHeap class

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

---

You should make use of the constructor initialiser list, e.g.,

Code:

---

// 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();
}

---

could be:

Code:

---

// constructor from vector
template<typename T>
MaxHeap<T>::MaxHeap(const std::vector<T>& v) : heap(v) {
        build_max_heap();
}

// constructor from array
template<typename T>
MaxHeap<T>::MaxHeap(T arr[], size_t size) : heap(arr, arr + size) {
        build_max_heap();
}

---

though I would prefer having a constructor that took a range specified by an iterator pair instead of one that had a (const reference to a) std::vector<T> as the parameter.

There are many places where the member function should have been declared const, but was not declared const.

By the way, under other circumstances, you might want to use std::make_heap, std::push_heap, std::pop_heap and possibly also std::sort_heap instead of implementing the algorithms yourself.

excellent, tx! constructor initializer is definitely better.

also looking now at make_heap() from <algorithm> the prototypes do allow a lot more generality:

Code:

---

template <class RandomAccessIterator>
  void make_heap ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void make_heap ( RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp );

---

that way your heap doesn't have to be a vector but can be an array or anything at all that supports random access iterators... nice!