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