// Author:  Douglas Wilhelm Harder
// Copyright (c) 2009 by Douglas Wilhelm Harder.  All rights reserved.

#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_HEAP
#define CA_UWATERLOO_ALUMNI_DWHARDER_HEAP

#include <cassert>

template <typename Type>
class Heap {
	private:
		int capacity;
		int size;

		Type *heap;

	public:
		Heap( int n ):
		capacity( std::max( 1, n + 1 ) ),
		size( 0 ),
		heap( new Type[capacity + 1] ) {
			// empty constructor
		}

		~Heap() {
			delete [] heap;
		}

		void push( Type const &obj ) {
			++size;

			int posn = size;

			while ( posn > 1 ) {
				int parent = posn/2;

				if ( heap[parent].priority() > obj.priority() ) {
					heap[posn] = heap[parent];

					posn = parent;
				} else {
					break;
				}
			}

			heap[posn] = obj;
		}

		Type top() const {
			assert( size != 0 );
			return heap[1];
		}

		void pop() {
			Type last = heap[size];

			--size;

			int posn = 1;

			while ( 2*posn < size ) {
				if (
					( last.priority() < heap[2*posn].priority() ) &&
					( last.priority() < heap[2*posn + 1].priority() )
				) {
					heap[posn] = last;
					return;
				}

				if ( heap[2*posn].priority() < heap[2*posn + 1].priority() ) {
					heap[posn] = heap[2*posn];
					posn = 2*posn;
				} else {
					heap[posn] = heap[2*posn + 1];
					posn = 2*posn + 1;
				}
			}

			if ( 2*posn == size && ( last.priority() > heap[2*posn].priority() ) ) {
				heap[posn] = heap[2*posn];
				heap[2*posn] = last;
			} else {
				heap[posn] = last;
			}
		}
};

#endif