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

# include <vector.h>
# include "prior.h"
# include <iostream.h>

template <class Iterator>
void make_heap (Iterator start, Iterator stop)
{
	unsigned int heapSize = stop - start;
	for (int i = heapSize / 2; i >= 0; i--)
			// assume children of node i are heaps
		adjust_heap(start, heapSize, i);
			// inv: tree rooted at node i is a heap
	// assert: structure is now a heap
}

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

template <class Iterator>
void heap_sort(Iterator start, Iterator stop)
{	// sort the vector argument using a heap algorithm

	// first build the initial heap
	make_heap (start, stop);

	// then convert heap into sorted collection
	sort_heap (start, stop);
}


void main() {
	vector<int> v(100);
	for (int i = 0; i < 100; i++)
		v[i] = rand();
	heap_sort(v.begin(), v.end());
	vector<int>::iterator itr = v.begin();
	while (itr != v.end()) {
		cout << *itr << " ";
		itr++;
		}
	// copy (v.begin(), v.end(), ostream_iterator<int>(cout, ":"));
	cout << "\n";
}