# ifndef priorityQueueH
# define priorityQueueH

//
//	simplified version of the STL priority queue data type
//		written by Tim Budd, Oregon State University, 1996

//	Described in Chapter 15 of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, budd@cs.orst.edu
//	Oregon State University
//

//	class priority_queue
//		a priority queue managed as a vector heap
//

template <class Container> class priority_queue {
public:
	typedef Container::value_type value_type;
	
	// priority queue protocol
	bool	empty	() { return c.empty(); }
	int		size	() { return c.size(); }
	value_type	top	() { return c.front(); }
	void	push (const value_type & newElement)
			{ c.push_back (newElement);
				push_heap(c.begin(), c.end()); }
	void	pop ()
			{ pop_heap (c.begin(), c.end()); 
				c.pop_back(); }
	void	display (char * text)
			{ cout << text;
			copy(c.begin(), c.end(), ostream_iterator<value_type>(cout, " "));
			cout << "\n";}
protected:
	Container	c;
};

template <class Iterator>
void push_heap (Iterator start, Iterator stop)
{
	// recreate heap after adding new element to end
	// assumption is that everything except last position
	// is legitimate heap
	
	unsigned int position = (stop - start) - 1;
	
	// now percolate up
	while (position > 0 && start[position] > start[(position-1)/2]) {
		swap(start[position], start[(position-1)/2]);
		// inv: tree rooted at position is a heap
		position = (position-1)/2;
		}
		
	// inv: tree rooted at position is a heap
	// inv: data holds a heap
}

template <class Iterator>
void adjust_heap (Iterator start, unsigned heapSize, unsigned position)
{
	while (position < heapSize) {
		// replace position with the larger of the 
		// two children, or the last element
		unsigned int childpos = position * 2 + 1;
		if (childpos < heapSize) {
			if ((childpos + 1 < heapSize) &&
				start[childpos + 1] > start[childpos])
					childpos += 1;
			if (start[position] > start[childpos]) {
				return;
				}
			else {
				swap (start[position], start[childpos]);
				}
			}
		position = childpos;
		}
}

template <class Iterator>
void pop_heap (Iterator start, Iterator stop)
{
	// move the largest element into the last location
	swap (*start, *--stop);
	
	// then readjust
	adjust_heap(start, stop - start, 0);
}

template <class Iterator>
void make_heap (Iterator start, Iterator stop)
{
	unsigned int max = stop - start;
	for (int i = max / 2; i >= 0; i--)
		adjust_heap (start, max, i);
}

template <class Iterator>
void sort_heap (Iterator start, Iterator stop)
{
	unsigned int max = stop - start;
	for (int i = max - 1; i > 0; i--) {
		swap(start[0], start[i]);
		adjust_heap(start, i, 0);
		}
}

template <class T>
void heap_sort (vector<T> & data)
{
	make_heap (data.begin(), data.end());	
	cout << "after making into heap: ";
	copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
	cout << "\n";

	sort_heap(data.begin(), data.end());
}

# endif