前言

上一小節,博主介紹了樹狀資料結構,其中提到了二叉樹的順序存盤與鏈式存盤.而二叉樹的順序存盤我們用的最多的就是 堆排序以及 選出前k個數(最小或最大),但是今天博主要介紹的就是 堆排序

順序存盤特點

用一個陣列從每一層開始,從上到下,從左到右進行存盤二叉樹中每一個結點中的值.如果有空結點,也需要占一個位置.

有人會問,這樣進行存盤我們怎么知道雙親結點(父節點)與其左右孩子的關系呢?答案是 二叉樹中雙親節點與孩子結點下標滿足一定的關系,可以用公式進行表示出來

左右孩子結點與雙親結點的下標關系如下:

• leftchild = parent * 2 + 1
• rightchild = parent * 2 + 2

雙親結點與孩子結點的下標的關系如下

• parent = ( leftchild - 1 ) / 2
• parent = ( rightchild - 2 ) / 2

但是大家仔細想想雙親結點與孩子結點的關系是否可以優化一下?沒錯,優化如下:

• parent = (child - 1) / 2,理由是在C語言中,運算子/遵循向下取整,所以上面的兩個式子可以用下面一個式子代替.

清楚資料結構----堆

堆是二叉樹中的一些特殊資料,其中分為大堆與小堆,并且只有符合大堆或者小堆的特性的二叉樹才能叫做堆.

• 大堆 二叉樹中所有的雙親結點值(父結點)都大于其對應的孩子結點的值.
• 小堆 二叉樹中所有的雙親結點值(父結點)都小于其對應的孩子結點的值.

如下圖所示,展示兩種結構:

大家發現無論是大堆還是小堆,都有一個特性嗎?什么特性呢?

最值都是在陣列索引為0處. 大家記住這個特點,后面會用到哦.

堆排序

即隨機給出一個陣列,我們想要利用堆的特性進行排序,該怎么進行排序呢?

比如有陣列num[] = {4,5,1,3,9,7,8,6,2,8,4};

我們既然想要利用堆特性進行對此陣列排序,那么我們的第一步一定是把此陣列變成堆(該程序稱為建堆),大家想想有什么辦法把它變成堆?

答案是:向下調整法

向下調整法

向下調整法的前提是除了根結點以外,其所有子樹都符合小堆或者大堆的特性.

比如陣列 num[] = {6,7,8,6,2,1,3};其樹狀結構如圖:

對于向上面的陣列便可以使用向下調整法,我們下面以要構建小堆為例.

向下調整法的介紹:

假設有一個陣列num[] = {6,3,2,5,4,3,7,8,9,6,8,5,9,8,8,9,9,8,7,7,9,7,6,6};(符合向下調整法的前提),因為除了根結點之外,其余都符合小堆特性,所以為了構建一個完整的堆,我們就需要把根結點移動到相應的位置,其移動程序示意圖如下:

我們仔細觀察上述動圖程序,發現向下調整法步驟如下:

1. 判斷左右孩子中誰最小.

2. 如果雙親結點比最小孩子大,就交換兩個結點值,否則調整完畢

3. 一直重復此操作,若調整到已沒有孩子結點,則調整結束

第一步:判斷左右孩子結點誰更小.

child = parent*2+1; //我們先假設左孩子更小.
if(child+1<n && num[child+1] < num[child])   //n是陣列長度
{
    child++;
} 
//如果右孩子更小,就把最小孩子更新到右孩子.
//之所以有條件child+1<n,是考慮上圖二叉樹最后只有一個孩子結點時候,那么默認最小值就只要左孩子,不需要與右孩子比較

第二步:判斷是否交換雙親結點與孩子結點值

void Swap(int*a,int*b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

if(num[parent] > num[child])
{
    Swap(&num[parent] , &num[child]);
    parent = child;              //交換值以后,重新更新雙親結點
    child = parent*2+1;          //交換值以后,重新默認新的左孩子為最小值.
}
else
{
    break; //否則結束回圈.
}

第三步:重復上述步驟

while(child < n) //child<n 代表沒有子節點了,就結束調整
{
    //偽代碼
    第一步代碼;
    第二步代碼;
}

所以向下調整法的代碼步驟為:

void Swap(int*a,int*b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
    
void AdjustDown(int num[],int n,int parent)   //n是陣列長度
{
    child = parent*2+1; //我們先假設左孩子更小.
    
	while(child<n)
    {
        if(child+1<n && num[child+1] < num[child])
        {
            child++;
        } 
        
        if(num[parent] > num[child])
        {
            Swap(&num[parent] , &num[child]);
            parent = child;              //交換值以后,重新更新雙親結點
            child = parent*2+1;          //交換值以后,重新默認新的左孩子為最小值.
        }
        else
        {
            break; //否則結束回圈.
        }
    }
}

建堆

向下調整法中,我們已經發現了,想要向下調整必須滿足向下調整的條件,但是我們想要的是對隨機陣列進行排序,所以除了向下調整外,我們還應該怎樣做,才能達到真正的建堆操作??.

答案: 我們反向行走,從最底層,最右邊的子樹開始進行調整,然后從右向左,從下到上.

比如有陣列num[] = {4,3,9,8,1,6,7,5,2,9,7,6,1,3};,我們的向下調整資料步驟如下:

所以建堆代碼如下:

for(int parent = (n-1-1)/2;parent>=0;parent--)  //n-1是最后一層最右邊結點的索引.(n-1-1)/2就是其雙親結點索引
{
    AdjustDown(num,n,parent);
}

排序

既然我們已經對隨機陣列建立好堆結構,那么剩下的就是進行**堆排序.**但是到這一步后就產生了一個誤區,什么誤區呢?

我們想要排升序,就應該建立小堆.

我們想要排降序,就應該建立大堆. 對嗎?答案是不對,這會讓時間復雜度變得極高.

正確的答案是,如果想要排升序,就應該建立大堆,想要排降序,就應該建立小堆.如果不相信的人,大家可以試試升序建小堆,看看怎樣進行排序,就會發現及其復雜,由于篇幅有限,博主就不再贅述.

由于我們已經建立好小堆,我們就以排列降序為例,仍是陣列num[] = {4,3,9,8,1,6,7,5,2,9,7,6,1,3};

我們利用堆結構中最值總是在索引為0處特點進行排序.首先把最小值和最后一個值進行交換,然后又對[0,n-2]索引中的數進行向下調整,不斷重讀此步驟,如圖(下面只是演示了排序程序中的部分步驟,因為后續步驟都是一樣的進行重復):

所以按照上述步驟,我們的堆排序(降序)程序代碼如下:

void HeapSort(int num[],int n)
{
    //建小堆
    for(int parent = (n-1-1)/2;parent>=0;parent--)
    {
         AdjustDown(num,n,parent);
    }
    
    for(int end = n-1;end>0;end--)  //end不用為0是因為最后還剩一個時候不用再交換.
    {
        Swap(&num[0],&num[end]);
      	AdjustDown(num,end,0);
    }
}

堆排序總代碼

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void AdjustDown(int num[],int n,int parent)
{
	int leftchild = parent * 2 + 1;
	while (leftchild < n)
	{
		if (leftchild + 1 < n && num[leftchild] > num[leftchild + 1])
		{
			leftchild++;
		}

		if (num[parent] > num[leftchild])
		{
			Swap(&num[parent],&num[leftchild]);
			parent = leftchild;
			leftchild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int num[], int n)
{
	//建小堆
	for (int parent = (n - 1 - 1) / 2; parent >= 0; parent--)
	{
		AdjustDown(num, n, parent);
	}

    
    //交換首位值,然后排除最后一個位置,重新向下調整
	for (int end = n - 1; end > 0; end--)  //end不用為0是因為最后還剩一個時候不用再交換.
	{
		Swap(&num[0], &num[end]);
		AdjustDown(num, end, 0);
	}
}

測驗

陣列num[] = {4,3,9,8,1,6,7,5,2,9,7,6,1,3};,使用上述代碼進行堆排序以后的結果為:

排序成功!!!