C++實現堆排序實例介紹

概述:

堆排序是利用構建“堆”的方法確定具有最大值的數據元素,並把該元素與最後位置上的元素交換。可將任意一個由n個數據元素構成的序列按照(a1,a2,…,an),按照從左到右的順序按層排列構成一棵與該序列對應的完全二叉樹。

一棵完全二叉樹是一個堆,當且僅當完全二叉樹的每棵子樹的根值ai≥其左子樹的根值a2i,同時ai≥其右子樹的根值a 2i+1 (1<i<n/2)。

實現堆排序需要實現兩個問題:

如何由無序序列建成一個堆?如何在輸出堆頂元素之後,調整剩餘元素成為一個新的堆?

思路:

堆排序算法思想:

1、從最後一個非葉子節點逐步到樹根,對每個子樹進行調整堆。

2、重復n-1次如下處理:將堆的根與最後一個葉子交換,除最後一個葉子之外剩餘部分再調整為堆。

調整堆算法思想:

1、將樹根與其左右子樹根值最大者交換;(大頂堆)

2、對交換後的左(或右)子樹重復過程1,直到左(或右)子樹為堆。

時間復雜度O(nlogn)

代碼:

調整堆算法:

void HeapAdjust(int *array,int i,int length){	//調整堆 
	int leftChild=2*i+1;		//定義左右孩子 
	int rightChild=2*i+2;
	int max=i;		//初始化,假設左右孩子的雙親節點就是最大值 
	if(leftChild<length&&array[leftChild]>array[max]){
		max=leftChild;
	}
	if(rightChild<length&&array[rightChild]>array[max]){
		max=rightChild;
	}
	if(max!=i){		//若最大值不是雙親節點,則交換值 
		swap(array[max],array[i]);
		HeapAdjust(array,max,length);	//遞歸,使其子樹也為堆 
	}
}

堆排序算法:

void HeapSort(int *array,int length){	//堆排序 
	for(int i=length/2-1;i>=0;i--){		//從最後一個非葉子節點開始向上遍歷,建立堆 
		HeapAdjust(array,i,length);
	}
	for(int j=length-1;j>0;j--){		//調整堆 ,此處不需要j=0  
		swap(array[0],array[j]);
		HeapAdjust(array,0,j);		//因為每交換一次之後,就把最大值拿出(不再參與調整堆),第三個參數應該寫j而不是length 
		Print(array,length); 
	}
}

完整代碼:

//堆排序
#include <iostream> 
using namespace std;
void Print(int array[],int length){	//每執行一次打印一次序列 
	for(int i=0;i<length;i++){
		cout<<array[i]<<" ";
	}
	cout<<endl;
}
void HeapAdjust(int *array,int i,int length){	//調整堆 
	int leftChild=2*i+1;		//定義左右孩子 
	int rightChild=2*i+2;
	int max=i;		//初始化,假設左右孩子的雙親節點就是最大值 
	if(leftChild<length&&array[leftChild]>array[max]){
		max=leftChild;
	}
	if(rightChild<length&&array[rightChild]>array[max]){
		max=rightChild;
	}
	if(max!=i){		//若最大值不是雙親節點,則交換值 
		swap(array[max],array[i]);
		HeapAdjust(array,max,length);	//遞歸,使其子樹也為堆 
	}
}
void HeapSort(int *array,int length){	//堆排序 
	for(int i=length/2-1;i>=0;i--){		//從最後一個非葉子節點開始向上遍歷,建立堆 
		HeapAdjust(array,i,length);
	}
	for(int j=length-1;j>0;j--){		//調整堆 ,此處不需要j=0  
		swap(array[0],array[j]);
		HeapAdjust(array,0,j);		//因為每交換一次之後,就把最大值拿出(不再參與調整堆),第三個參數應該寫j而不是length 
		Print(array,length); 
	}
}
int main(){
	int array[]={49,38,65,97,76,13,27,49};
	int length=sizeof(array)/sizeof(*array);
	Print(array,length);			//先打印原始序列 
	HeapSort(array,length);
	return 0;
}

運行示例:

第一行是原始序列,第二到八行分別是經過7次調整堆所得到的序列。

到此這篇關於C++實現堆排序實例介紹的文章就介紹到這瞭,更多相關C++堆排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: