#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
*/本篇參考了acwing算法基礎課。
