C++ 堆排

堆排的一開始要先建堆，這裡是按從小到大排序，建立的是最大堆。注意這裡的堆排要求數組的下标是從一開始，友善操作。

堆排序的兩個步驟：

（1）從非葉子結點開始依次“下沉”，建構出最大堆。

（2）依次将堆頂元素删除，此時新交換的根結點要”下沉".

#include <iostream>
using namespace std;

void shift(int arr[],int low,int high){
	int i=low,j=2*i;
	int temp = arr[i];
	while(j<=high){
		while(j < high && arr[j+1]>arr[j])
			j++;
		if(temp < arr[j]){
			arr[i] = arr[j];
			i = j;
			j = 2*i;
		}else
			break;
	}
	arr[i] = temp; 
}

void heapSort(int arr[],int n){
	for(int i=n/2;i>=1;i--)//第一步是建堆 
		shift(arr,i,n);
	for(int i=n;i>=2;i--){//依次删除節點
		int temp = arr[1];
		arr[1] = arr[i];
		arr[i] = temp;
		shift(arr,1,i-1);
	}
} 

int main(){
	int arr[] = {0,43,65,6,43,78,342,78,34};//從下标一開始 
	heapSort(arr,8);
	for(int i=1;i<=8;i++)
		cout<<arr[i]<<" "; 
	
	return 0;
}
           

運作結果如下:

下面補充STL源碼中對于堆的建堆make_heap、排序sort_heap，以及push_heap、pop_heap操作

上面示例中的堆排序包含了建堆make_heap和sort_heap兩個操作

heap概述 注意：heap不屬于STL容器元件，隻是扮演優先隊列的助手。heap算法包括： push_heap、pop_heap、make_heap、sort_heap等函數 底層實作：用vector代替array   (1) push_heap算法 對于一個最大堆，新加入結點放在最後一個，并采用"上浮"操作（隻需判斷目前結點值和父結點值大小，以此判别是否上浮)

  (2) pop_heap算法 将最後一個元素與第一個元素替換，并進行"下浮"操作(左右子孩子結點需要先進行比較，與較小(或較大)的孩子結點進行交換)  

  注意： pop_heap之後，最大元素隻是放在容器最尾端，将它取走可用vector提供的back()操作

  (3)sort_heap算法 每次用pop_heap操作，都可以得到目前最大值，以此進行 

  (4)make_heap算法 将一段現在資料轉化為一個heap,注意排序是從第一個非葉子結點開始