Heap sort

heapSort.cpp

/*
max heap
*/
#include <iostream>
using namespace std;
int capacity=0;
int maxCapacity=64;
void maxHeapify(int* a, int k, int n){
	int left=2*k+1;
	int right=2*k+2;
	int big=k;
    if(left<n && right<n){
    	if(a[left]>a[big]){
			big=left;
		}
		if(a[right]>=a[big]){
			big=right;
		}
		if(big!=k){
			swap(a[big], a[k]);
			maxHeapify(a, big, n);
		}
    }
}
void heap(int* a, int n){
	for(int i=n/2-1;i>=0;i--){
		maxHeapify(a, i, n);
	}

}
int extract(int* a){
	int maxElem=a[0];
	a[0]=a[capacity-1];
	capacity--;
	maxHeapify(a, 0, capacity);
	return maxElem;
}
void insertElement(int* a, int elem){
	int i=capacity;

	if(++capacity<maxCapacity){
		a[i]=elem;

		while(i>0 && a[i]>a[(i-1)/2]){
			swap(a[i], a[(i-1)/2]);
			i=(i-1)/2;
		}
	}
}
int main(){

	int a[]={9, 1, 4, 5, 3, 2, 7, 5, 3, 5, 4};
	int n=sizeof(a)/sizeof(a[0]);
	capacity=n;
	heap(a, n);
	for(int i=0;i<capacity;i++){
		cout << a[i] << " ";
	}
	cout << endl;
	cout << extract(a) << endl;
	for(int i=0;i<capacity;i++){
		cout << a[i] << " ";
	}
	cout << endl;

	insertElement(a, 16);

	for(int i=0;i<capacity;i++){
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}