堆排序（算法导论实现）

#include <iostream>
#include <vector>
using namespace std;

int heap_size;

int left(int i){
	return 2 * i + 1;
}

int right(int i){
	return 2 * i + 2;
}

void exchange(vector<int>& v, int k, int largest){
	int temp = v[k];
	v[k] = v[largest];
	v[largest] = temp;
}

void max_heapify(vector<int>& v, int k){
	int l = left(k), r = right(k);

	int largest;
	if(l <= heap_size - 1 && v[l] > v[k])
		largest = l;
	else
		largest = k;

	if(r <= heap_size - 1 && v[r] > v[largest])
		largest = r;
	
	if(largest != k){
		exchange(v, k, largest);
		max_heapify(v, largest);
	}
}

void build_max_heap(vector<int>& v){
	for(int i = heap_size/2 - 1; i >= 0; i--){
		max_heapify(v, i);
	}
}

void heap_sort(vector<int>& v){
	build_max_heap(v);
	for(int i = v.size() - 1; i > 0; i--){
		exchange(v, 0, i);
		heap_size -= 1;
		max_heapify(v, 0);
	}
}

int main(){  
	 /* 3, 5, 6 ,8, 2, 1, 9, 4, 0, 7 */
	vector<int> v;
	v.push_back(3);v.push_back(5);v.push_back(6);v.push_back(8);v.push_back(2);
	v.push_back(1);v.push_back(9);v.push_back(4);v.push_back(0);v.push_back(7);
	
	heap_size = v.size();

	heap_sort(v);

	for(int i = 0; i < 10; i++){  
		cout << v[i] << " ";
	}  
	system("PAUSE");  
}  #include <iostream>
#include <vector>
using nam