24小時(shí)聯(lián)系電話:18217114652、13661815404
中文
- 您當(dāng)前的位置：
- 首頁(yè)>
- 電子資訊>
- 技術(shù)專(zhuān)題>
- 二進(jìn)制堆排序算法說(shuō)明
技術(shù)專(zhuān)題
二進(jìn)制堆排序算法說(shuō)明
二進(jìn)制堆排序算法說(shuō)明
二進(jìn)制堆排序算法使用二進(jìn)制樹(shù)執(zhí)行排序操作。二叉樹(shù)是由數(shù)組中的元素構(gòu)建而成的結(jié)構(gòu)，如下圖所示以樹(shù)的形式顯示。二進(jìn)制堆樹(shù)有兩種類(lèi)型，max-heap和min-heap。
同樣值得注意的是，還有其他排序算法，例如Bubble排序，Selection排序，Insertion排序和Merge排序來(lái)對(duì)給定數(shù)組中的元素進(jìn)行排序。
當(dāng)涉及二進(jìn)制堆排序算法時(shí)，它有兩種類(lèi)型。
最大堆二叉樹(shù)，其父節(jié)點(diǎn)大于或等于其每個(gè)子節(jié)點(diǎn)。上面顯示的堆樹(shù)是最大堆樹(shù)的示例。
最小堆二叉樹(shù)，其中所有父節(jié)點(diǎn)均小于或等于其每個(gè)子節(jié)點(diǎn)。
堆排序通過(guò)刪除節(jié)點(diǎn)中最大或最小的元素并將其放入數(shù)組中來(lái)執(zhí)行排序。每次提取之后，將更新堆以維護(hù)堆屬性。為了更好地解釋這一點(diǎn)，請(qǐng)看以下示例
二進(jìn)制堆排序算法說(shuō)明：
考慮以下具有五個(gè)數(shù)字的數(shù)組。我們需要使用Max-heap以升序?qū)λM(jìn)行排序。
讓我們根據(jù)給定的數(shù)字?jǐn)?shù)組構(gòu)造一個(gè)完整的二叉樹(shù)。通過(guò)以這種方式排列數(shù)組中的元素來(lái)構(gòu)造樹(shù)，使其形成具有父節(jié)點(diǎn)和子節(jié)點(diǎn)的樹(shù)狀數(shù)據(jù)結(jié)構(gòu)。
該樹(shù)必須是完整的二叉樹(shù)才能成為堆數(shù)據(jù)結(jié)構(gòu)。有兩種類(lèi)型的節(jié)點(diǎn)，父節(jié)點(diǎn)和子節(jié)點(diǎn)。子節(jié)點(diǎn)是附加到單個(gè)節(jié)點(diǎn)（即其父節(jié)點(diǎn)）的節(jié)點(diǎn)。在下面的二叉樹(shù)中，15是父節(jié)點(diǎn)，7和43是其子節(jié)點(diǎn)。同樣，在下一級(jí)的二叉樹(shù)7中，父節(jié)點(diǎn)– 25和5是子節(jié)點(diǎn)。
我們需要將父節(jié)點(diǎn)與子節(jié)點(diǎn)（7、25、5）進(jìn)行比較。
其中最大的25個(gè)。
7會(huì)被25交換，因?yàn)樗笥?span>7。
將節(jié)點(diǎn)25和43與它的父節(jié)點(diǎn)43進(jìn)行比較。
15在父節(jié)點(diǎn)中將被替換為43，因?yàn)橄啾榷?，它在其他兩個(gè)節(jié)點(diǎn)中最大。
因此，我們得到了我們的最大堆
現(xiàn)在我們需要構(gòu)造排序后的數(shù)組。為此，涉及三個(gè)步驟。
交換
去掉
堆肥
首先將根節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)交換。因?yàn)槲覀冎肋@是最大堆，所以根節(jié)點(diǎn)在所有節(jié)點(diǎn)中最大，而5在最小節(jié)點(diǎn)中。
刪除數(shù)字43
通過(guò)將最大值放在根節(jié)點(diǎn)或堆中來(lái)重建堆
用7交換25
移除25
通過(guò)將15放在頂部來(lái)進(jìn)行堆肥
以7交換15
移除15
用5交換7
刪除7
然后我們得到排序的數(shù)組
然后我們得到排序的數(shù)組
實(shí)現(xiàn)二進(jìn)制堆排序算法的步驟：
從輸入元素創(chuàng)建二叉樹(shù)
您需要根據(jù)需要執(zhí)行的排序類(lèi)型將其設(shè)置為最大堆或最小堆。
比較父節(jié)點(diǎn)和子節(jié)點(diǎn)
用最大的子節(jié)點(diǎn)替換父節(jié)點(diǎn)
對(duì)所有父節(jié)點(diǎn)執(zhí)行相同的操作
重復(fù)直到對(duì)二叉樹(shù)中的所有節(jié)點(diǎn)進(jìn)行排序并獲得最大堆
然后將根節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)交換
刪除該節(jié)點(diǎn)，因?yàn)檫@是最大值，并根據(jù)排序順序?qū)⑵浞湃霐?shù)組的最右側(cè)或數(shù)組的最左側(cè)
通過(guò)將最大值放到根節(jié)點(diǎn)或heapify來(lái)重建堆
將根節(jié)點(diǎn)與最右邊的子節(jié)點(diǎn)進(jìn)行比較
重復(fù)相同的過(guò)程，直到所有節(jié)點(diǎn)都被整理到陣列中
二進(jìn)制堆排序算法的示例代碼：
#include <stdio.h>
//交換兩個(gè)元素位置的函數(shù)
void swap（int * a，int * b）{
int temp = * a;
* a = * b;
* b =溫度；
}
void heapify（int arr []，int n，int i）{
//在根，左子和右子中找到最大的
int最大= i;
左整數(shù)= 2 * i + 1;
正確的整數(shù)= 2 * i + 2;
如果（左<n && arr [left]> arr [largest]）
最大=左；
如果（正確<n && arr [正確]> arr [最大]）
最大=正確；
//如果根不是最大，交換并繼續(xù)堆
如果（最大！= i）{
swap（＆arr [i]，＆arr [large]）;
heapify（arr，n，最大）;
}
}
//主函數(shù)做堆排序
void heapSort（int arr []，int n）{
//建立最大堆
對(duì)于（int i = n / 2-1; i> = 0; i--）
heapify（arr，n，i）;
//堆排序
對(duì)于（int i = n-1; i> = 0; i--）{
swap（＆arr [0]，＆arr [i]）;
//重整根元素以再次在根上獲得最高元素
heapify（arr，i，0）;
}
}
//打印數(shù)組
void printArray（int arr []，int n）{
對(duì)于（int i = 0; i <n; ++ i）
printf（“％d”，arr [i]）;
printf（“ \ n”）;
}
//主要代碼
int main（）{
int arr [] = {15，7，43，25，5};
int n = sizeof（arr）/ sizeof（arr [0]）;
heapSort（arr，n）;
printf（“排序數(shù)組為\ n”）;
printArray（arr，n）;
}