牛骨文教育服务平台(让学习变的简单)

       堆的基本操作参考文章:堆的基本操作

       对于小根堆来说,一般的思路是每次删除最小值,执行N次删除;每次将删除的元素拷贝到一个新的数组,那么新数组将按照从小到大的顺序排列。这里的主要问题是空间的:使用新数组,使存储空间增加了一倍。

       一个技巧是:每次删除一个堆元素,堆大小会减少1。那么位于堆最后的那个空间可以用来存放刚刚被删除的元素。按照这种思路,不用额外的空间即可完成排序。

      对小根堆,该方式排序完的数组是递减的,那么,如果我们建立堆时用大根堆,则该方式得到的排序结果是递增的。

      堆排序中用到了下滤操作,因为堆排序其实就是堆删除的一系列操作,而堆的删除操作会下滤,参考二叉堆的插入删除等操作C++实现

      在移动堆元素的时候(AdjustHeap函数中),用到了一个技巧来减少交换元素的次数,参考插入排序和希尔排序,这里不再赘述。

/*
(大根)堆排序,花费O(NlogN)。
*/
template<typename T>
void HeapSort(vector<T>& a) {
	int i;
	//先建立大根堆,该操作花费O(N)
	for (i = a.size() / 2; i >= 0; --i) {
		AdjustHeap(a, i, a.size());
	}
	//将要删除的元素放入堆末尾的空间(交换根元素和尾元素),
	//这样不需要额外的空间。
	for (i = a.size() - 1; i > 0; --i) {
		T tmp = a[i];
		a[i] = a[0];
		a[0] = tmp;
		/*
		每次删除时,根元素与根末尾元素交换了,在位置0处下滤。
		由于不断从堆中删除,因此堆大小不断减小,为i
		*/
		AdjustHeap(a, 0, i);
	}
}

//该函数是堆操作中的下滤操作
template<typename T>
void AdjustHeap(vector<T>&a, int pos, int n) {
	int pos_child;
	T tmp;
	for (tmp = a[pos]; (pos * 2 + 1) < n; pos = pos_child) {
		pos_child = 2 * pos + 1;
		if (pos_child != n -1 && a[pos_child] < a[pos_child + 1])
			pos_child++;
		if (tmp < a[pos_child])
			a[pos] = a[pos_child];
		else
			break;
	}
	a[pos] = tmp;
}

//只是一个打印元素的函数
template<typename T>
void PrintValue(vector<T>& a) {
 vector<T>::iterator iter = a.begin();
 while (iter != a.end()) {
     cout << *iter++ << " ";
 }
 cout << endl;
}
int main() {
 int value;
 vector<int> ivec; 
 while (cin >> value)
     ivec.push_back(value);
 HeapSort<int>(ivec);
 PrintValue(ivec);
}