Heap Sort

www.geeksforgeeks.org/heap-sort/

 

#inclulde <stdio.h>

static int heap[10] = { 9, 2, 3, 7, 5, 1, 4, 6, 8, 15 };

void swap(int* arr, int i, int j) {
	int tmp = arr[j];
    arr[i] = arr[j];
    arr[j] = tmp;
}

void heapify(int* arr, int n, int i) {
	
    int p = i; 
    int l = i * 2 + 1; //left
    int r = i * 2 + 2; //right

	if ( l < n && arr[l] > arr[p]) {
    	p = l;
    }
    
    if ( r < n && arr[r] > arr[p]) {
    	p = r;
    }
    
    if (i != p) {
    	swap(arr, i, p);
    	heapify(arr, n, p);
    }    
}

void heapSort(int* arr, int n, int i) {

	//build max heap
	for (int i = n / 2 - 1; i >= 0; i--) {
    	heapify(arr, n, i);
    }
    
    for (int i = n - 1; i > 0; i--) {
    	swap(arr, 0, i);
        heapify(arr, i, 0);
    }
}

int main() {

	heapsort2(heap, 10);
	for ( int i = 0; i < 10; i++ ) {
    	printf("%d, ", heap[i]);
    }
}