ProAnswers.org

algorithm Heap Sort

algorithm Heap Sort

#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

	void max_heapify(int list[], int i, int heap_size){

	    int l, r, largest, temp;

	    l = 2 * i;

	    r = (2 * i) + 1;

	    largest = i;

	    if(l <= heap_size && list[l - 1] > list[i - 1]) largest = l;

	    if(r <= heap_size && list[r - 1] > list[largest - 1]) largest = r;

	    if(largest != i){

	        SWAP(list[i - 1], list[largest - 1], temp);

	        max_heapify(list, largest, heap_size);

	    }

	}

	 

	void build_maxheap(int list[], int length){

	    int heap_size, i;

	    heap_size = length;

	    i = length / 2;

	    while(i >= 1){

	        max_heapify(list, i, heap_size);

	        i--;

	    }

	}

	 

	void heapsort(int list[], int length){

	    int i, heap_size, temp;

	    heap_size = length;

	    build_maxheap(list, length);

	    for(i = length; i >= 2; i--){

	        SWAP(list[0], list[i - 1], temp);

	        heap_size--;

	        max_heapify(list, 1, heap_size);

	    }

	}