堆排序
堆排序是一种利用堆这种数据结构所设计的排序算法。堆是一个特殊的树形数据结构,通常用于实现优先队列。堆有两个主要的类型:最大堆和最小堆。在最大堆中,父节点的值总是大于或等于其子节点的值;而在最小堆中,父节点的值总是小于或等于其子节点的值。
堆排序主要利用最大堆进行排序。以下是堆排序的基本步骤:
- 创建最大堆:首先将待排序的数组(或列表)构建成一个最大堆。这个过程从最后一个非叶子节点开始,将这个节点与它的父节点进行比较,如果该节点的值小于父节点,就交换它们的位置,如此循环直到堆中只剩下一个节点。
- 堆顶元素与末尾元素交换:此时,将堆顶元素(最大值)与末尾元素交换。这样,末尾元素就成为新的最大值,而堆顶元素则被“下沉”到正确的位置。
- 调整剩余元素:将新的末尾元素看作是“根”,然后重新执行步骤2,直到堆中只剩下一个节点。
在这个过程中,每次都将当前的最大值移到正确的位置,并把剩余的元素重新调整为最大堆。最终,当所有元素都被移动到正确的位置时,就完成了排序。
总的来说,堆排序是一种高效的排序算法,它的时间复杂度为O(n log n),其中n是待排序元素的数量。然而,它的空间复杂度较高,为O(1),因为不需要额外的存储空间来进行排序。
小根堆
众所周知,设当前结点索引为i,左子树结点索引为i2,右子树结点索引为i2+1
#include<iostream>
using namespace std;
const int N = 100010;
int s[N], head;
void down(int u){
int k = u;
// 两种情况:
// 如果只有一个子树满足条件,那么直接与其交换
// 如果两个子树满足条件,那么先更新一个子树,另一个子树等待当前结点父结点往下遍历时更新,最终到达根节点,所有未更新子树全部更新成功
if(u * 2 <= si && s[u * 2] <= s[k]) k = u * 2; // 左子树
if(u * 2 + 1 <= si && s[u * 2 + 1] <= s[k]) k = u * 2 + 1; // 右子树
if(k!=u){
// 如果有子树比当前结点小
swap(s[k], s[u]);
down(k); // 继续往子树遍历
}
}
int main(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> s[i];
head=n; // 记录数组长度
for(int i = n / 2; i > 0; i--) down(i); // 从非叶子结点最下层往上遍历
for(int i = 1; i <= n; i++) cout << s[i] << ' ';
}
大根堆
#include<iostream>
using namespace std;
const int N = 100010;
int s[N], si;
void up(int u){
int k = u;
if(u * 2 <= si && s[u * 2] >= s[k]) k = u * 2;
if(u * 2 + 1 <= si && s[u * 2 + 1] >= s[k]) k = u * 2 + 1;
if(k!=u){
swap(s[k], s[u]);
up(k);
}
}
int main(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> s[i];
si= n;
for(int i = n / 2; i > 0; i--) up(i);
for(int i = 1; i <= n; i++) cout << s[i] << " ";
}
文章评论