当前位置：首页 > backend >正文

堆排序（算法题）

backend 2025/5/8 13:59:58

在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;const int N = 100010;  // 堆数组的最大容量
int h[N], s;           // h[]存储堆元素，s表示当前堆的大小// 下沉操作：调整以i为根的子树，维护小顶堆性质
void down(int i) {int t = i;  // t记录当前节点及其子节点中的最小值位置// 检查左子节点（2*i）是否存在，若更小则更新tif (2 * i <= s && h[i] > h[2 * i]) t = 2 * i;// 检查右子节点（2*i+1）是否存在，且是否比当前t位置的更小if (2 * i + 1 <= s && h[t] > h[2 * i + 1]) t = 2 * i + 1;// 若t发生变化，说明需要交换并继续调整if (t != i) {swap(h[t], h[i]);  // 交换当前节点与更小的子节点down(t);           // 递归调整交换后的子树}
}int main() {int n, m;cin >> n >> m;        // 输入元素总数n和需要输出的前m小元素个数for (int i = 1; i <= n; i++) cin >> h[i];  // 输入数组（堆的初始状态）s = n;  // 初始化堆大小为n// 构建初始堆：从最后一个非叶子节点开始，自底向上调整// 模拟：例如n=5时，i从2开始处理，然后i=1。每个节点下沉到合适位置// 这样可以更短的时间复杂度构建for (int i = n / 2; i; i--) down(i);// 输出前m小元素：每次取堆顶（最小值），然后维护堆while (m--) {cout << h[1] << ' ';  // 输出当前堆顶（最小元素）// 删除堆顶操作：用最后一个元素覆盖堆顶，堆大小减1h[1] = h[s]; s--;// 调整新堆顶元素，使其下沉到合适位置// 模拟：例如将原本最后的元素放到堆顶后，可能破坏堆结构，需要逐层比较下沉down(1); }return 0;
}/*
模拟示例（n=5, m=3，初始数组[3,1,2,4,5]）：
1. 初始建堆：- i=2（元素1）：无子节点，无需调整- i=1（元素3）：- 比较左子节点1（更小），交换3和1 → 数组[1,3,2,4,5]- 递归调整位置2（原3）：- 比较子节点4和5，无需调整
2. 第一轮输出：- 输出1 → 堆顶替换为5，s=4 → 数组[5,3,2,4]- 调整堆顶5：- 左子3 > 右子2，交换5和2 → [2,3,5,4]- 递归调整位置3（5），无子节点，停止
3. 第二轮输出：- 输出2 → 堆顶替换为4，s=3 → 数组[4,3,5]- 调整堆顶4：- 左子3更小，交换4和3 → [3,4,5]
4. 第三轮输出：- 输出3 → 堆顶替换为5，s=2 → 数组[5,4]- 调整堆顶5：- 左子4更小，交换 → [4,5]
最终输出序列：1 2 3
*/