算法1

(左偏树) $O(nlogn)$

跟二叉堆比起来， 左偏树的代码容易记忆，没有shiftup,shiftdown， 只有一个操作merge, 含义就是合并两个堆，一个新节点就相当于一个元素的堆，删除元素相当于合并根的左右孩子组成的堆。
同时堆合并时效率更高。

C++ 代码

#include <iostream>

using namespace std;

const int N = 1e5 + 5;

int n, m;
int dist[N], rc[N], lc[N], val[N];

int merge(int x, int y){
    if (!x || !y) return x | y;
    if (val[x] > val[y]) swap(x, y);
    rc[x] = merge(rc[x], y);
    if (dist[lc[x]] < dist[rc[x]]) swap(lc[x], rc[x]);
    dist[x] = dist[rc[x]] + 1;
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    dist[0] = -1;
    int root;
    for (int i = 1; i <= n; i ++) {
        cin >> val[i];
        if (i == 1) root = i;
        else root = merge(root, i);
    }
    for (int i = 1; i <= m; i ++) {
        cout << val[root] << " ";
        root = merge(lc[root], rc[root]);
    }
    return 0;
}

外结点的概念：左右孩子至少有一个不存在的节点
左偏树上一个点i的距离dist[i]：定义为i到离它最近的外结点的距离
规定，空节点距离为-1, 那么叶子结点的距离为0
一个节点的距离等于它到外结点的距离，左偏树的左子树高度大于右子树高度，所以肯定是右子树离外结点更近
所以dist[i] = dist[rc[i]] + 1 , 1表示根节点这一层距离占1,

算法2

(斜堆) $O(nlogn)$

左偏树的简化版，每次合并时只固定与右孩子合并，再交换左右孩子,保持左边元素数量更多。 用法同左偏树。

C++ 代码

#include <iostream>

using namespace std;

const int N = 1e5 + 5;

int n, m;
int rc[N], lc[N], val[N]; //分别存储右孩子(right child),左孩子编号， 和值, lc[i]=0表示左孩子为空

int merge(int x, int y){ //要合并的两个堆堆顶元素编号
    if (!x || !y) return x | y;  // 相当于有一个为空, 就返回另一个,是递归边界条件
    if (val[x] > val[y]) swap(x, y);   //小根堆，堆顶元素小于孩子，默认让x为根
    rc[x] = merge(rc[x], y); // x最小，并且为根，  堆y要与x的右孩子合并，合并后变成新的右孩子
    swap(lc[x], rc[x]); // 合并后交换左右孩子，保持左孩子数量更多，右侧元素数量更少。
    return x; //返回新的堆堆顶元素编号
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    int root;
    for (int i = 1; i <= n; i ++) {
        cin >> val[i];
        if (i == 1) root = i; //第一次操作，生成的堆编号为1
        else root = merge(root, i); // 合并之前的堆和当前堆，当前堆编号为i, 可看成一个元素的堆
    }
    for (int i = 1; i <= m; i ++) {
        cout << val[root] << " "; //小根堆堆顶元素最小
        root = merge(lc[root], rc[root]); // 相当于删去根节点，合并根的左右孩子，形成新堆
    }
    return 0;
}