24小时联系电话:18217114652、13661815404
中文
技术专题
二进制堆排序算法说明
二进制堆排序算法说明
二进制堆排序算法使用二进制树执行排序操作。二叉树是由数组中的元素构建而成的结构，如下图所示以树的形式显示。二进制堆树有两种类型，max-heap和min-heap。
同样值得注意的是，还有其他排序算法，例如Bubble排序，Selection排序，Insertion排序和Merge排序来对给定数组中的元素进行排序。
当涉及二进制堆排序算法时，它有两种类型。
最大堆二叉树，其父节点大于或等于其每个子节点。上面显示的堆树是最大堆树的示例。
最小堆二叉树，其中所有父节点均小于或等于其每个子节点。
堆排序通过删除节点中最大或最小的元素并将其放入数组中来执行排序。每次提取之后，将更新堆以维护堆属性。为了更好地解释这一点，请看以下示例
二进制堆排序算法说明：
考虑以下具有五个数字的数组。我们需要使用Max-heap以升序对它进行排序。
让我们根据给定的数字数组构造一个完整的二叉树。通过以这种方式排列数组中的元素来构造树，使其形成具有父节点和子节点的树状数据结构。
该树必须是完整的二叉树才能成为堆数据结构。有两种类型的节点，父节点和子节点。子节点是附加到单个节点（即其父节点）的节点。在下面的二叉树中，15是父节点，7和43是其子节点。同样，在下一级的二叉树7中，父节点– 25和5是子节点。
我们需要将父节点与子节点（7、25、5）进行比较。
其中最大的25个。
7会被25交换，因为它大于7。
将节点25和43与它的父节点43进行比较。
15在父节点中将被替换为43，因为相比而言，它在其他两个节点中最大。
因此，我们得到了我们的最大堆
现在我们需要构造排序后的数组。为此，涉及三个步骤。
交换
去掉
堆肥
首先将根节点与最后一个节点交换。因为我们知道这是最大堆，所以根节点在所有节点中最大，而5在最小节点中。
删除数字43
通过将最大值放在根节点或堆中来重建堆
用7交换25
移除25
通过将15放在顶部来进行堆肥
以7交换15
移除15
用5交换7
删除7
然后我们得到排序的数组
然后我们得到排序的数组
实现二进制堆排序算法的步骤：
从输入元素创建二叉树
您需要根据需要执行的排序类型将其设置为最大堆或最小堆。
比较父节点和子节点
用最大的子节点替换父节点
对所有父节点执行相同的操作
重复直到对二叉树中的所有节点进行排序并获得最大堆
然后将根节点与最后一个节点交换
删除该节点，因为这是最大值，并根据排序顺序将其放入数组的最右侧或数组的最左侧
通过将最大值放到根节点或heapify来重建堆
将根节点与最右边的子节点进行比较
重复相同的过程，直到所有节点都被整理到阵列中
二进制堆排序算法的示例代码：
#include <stdio.h>
//交换两个元素位置的函数
void swap（int * a，int * b）{
int temp = * a;
* a = * b;
* b =温度；
}
void heapify（int arr []，int n，int i）{
//在根，左子和右子中找到最大的
int最大= i;
左整数= 2 * i + 1;
正确的整数= 2 * i + 2;
如果（左<n && arr [left]> arr [largest]）
最大=左；
如果（正确<n && arr [正确]> arr [最大]）
最大=正确；
//如果根不是最大，交换并继续堆
如果（最大！= i）{
swap（＆arr [i]，＆arr [large]）;
heapify（arr，n，最大）;
}
}
//主函数做堆排序
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）;
}
}
//打印数组
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（“排序数组为\ n”）;
printArray（arr，n）;
}