// heapsort.cpp

#include <iostream.h>
//#define itemMAX 0

typedef int itemType;

void swap(itemType a[], int p, int q);

class PQ {
	private:
		itemType *a;
		int N;
	public:
		PQ(int max)
			{ a = new itemType[max]; N = 0; }
		~PQ()
			{ delete a; }
		void insert(itemType v)
			{ a[++N] = v; upheap(N); }
/*		itemType remove() {
			int j, max = 1;
			for (j=2; j <= N; j++)
				if (a[j] > a[max]) max=j;
			swap(a, max, N);
			return a[N--];
		} */
		void upheap(int k);
		void downheap(int k);
		itemType remove();
		itemType replace(itemType v);
};

void PQ::upheap(int k) {
	itemType v;
	v = a[k]; a[0]=itemMAX;
	while (a[k/2] <= v)         			// havner i evig løkke her ...
		{ a[k] = a[k/2]; k = k/2; }
	a[k] = v;
}

void PQ::downheap(int k) {
	int j; itemType v;
	v = a[k];
	while (k <= N/2) {
		j = k+k;
		if (j<N && a[j]<a[j+1]) j++;
		if (v >= a[j]) break;
		a[k] = a[j]; k = j;
	}
	a[k]=v;
}

itemType PQ::remove() {
	itemType v = a[1];
	a[1]= a[N--];
	downheap(1);
	return v;
}

itemType PQ::replace(itemType v) {
	a[0]=v;
	downheap(0);
	return a[0];
}

//------------------------------------------------------------------------------
void heapsort(itemType a[], int N) {
	int i; PQ heap(N);
	for (i=1; i <= N; i++) heap.insert(a[i]);
	for (i=N; i >= 1; i--) a[i]=heap.remove();
}

//------------------------------------------------------------------------------
void swap(itemType a[], int p, int q)
{
	itemType t = a[p];
	a[p] = a[q];
	a[q] = t;
}
//------------------------------------------------------------------------------
void main() {
	itemType b[10]={3,3,76,234,5,89,2,6,12,3};
	int i;

	for (i=0; i<10; i++)
		cout << b[i] << "   ";
	cout << endl;

	heapsort(b, 10);

   for (i=0; i<10; i++)
		cout << b[i] << "   ";
	cout << endl;
}