c++堆排序简版

c++堆排序简版

堆排序

堆排序是一种利用堆这种数据结构所设计的排序算法。堆是一个特殊的树形数据结构，通常用于实现优先队列。堆有两个主要的类型：最大堆和最小堆。在最大堆中，父节点的值总是大于或等于其子节点的值；而在最小堆中，父节点的值总是小于或等于其子节点的值。

堆排序主要利用最大堆进行排序。以下是堆排序的基本步骤：

1. 创建最大堆：首先将待排序的数组（或列表）构建成一个最大堆。这个过程从最后一个非叶子节点开始，将这个节点与它的父节点进行比较，如果该节点的值小于父节点，就交换它们的位置，如此循环直到堆中只剩下一个节点。
2. 堆顶元素与末尾元素交换：此时，将堆顶元素（最大值）与末尾元素交换。这样，末尾元素就成为新的最大值，而堆顶元素则被“下沉”到正确的位置。
3. 调整剩余元素：将新的末尾元素看作是“根”，然后重新执行步骤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] << " ";
}