Thread: MaxHeap class

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    242

    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

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    242
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  2. Class design problem
    By h3ro in forum C++ Programming
    Replies: 10
    Last Post: 12-19-2008, 09:10 AM
  3. Defining derivated class problem
    By mikahell in forum C++ Programming
    Replies: 9
    Last Post: 08-22-2007, 02:46 PM
  4. matrix class
    By shuo in forum C++ Programming
    Replies: 2
    Last Post: 07-13-2007, 01:03 AM