AcWing | 堆排序

叁歲伎倆 2022-12-20 01:56 146阅读 0赞

**题目内容**

> 输入一个长度为n的整数数列，从小到大输出前m小的数。 输入格式
> 
> 第一行包含整数n和m。
> 
> 第二行包含n个整数，表示整数数列。

**输出格式**

> 共一行，包含m个整数，表示整数数列中前m小的数。

**数据范围**

> 1≤m≤n≤105 ， 1≤数列中元素≤109

**输入样例：**

5 3
    4 5 1 3 2

**输出样例：**

1 2 3

--------------------

**思路：**

*  堆：是一棵完全二叉树（即除了叶节点以外，所有节点都是非空，且叶节点从左到右排列）
    
     *  例如小根堆：每个节点都小于等于其左右子节点
 *  堆如何存储？
    
     *  设根节点为x，则其左儿子是2x，右儿子是2x+1
 *  堆的两个函数：因为一开始建堆的时候是没有考虑顺序的，所以要用这两个操作调整成小/大根堆
    
     *  down：节点下移
     *  up：节点上移
 *  堆的基本操作，对于小根堆，且下标从1开始：
    
     *  插入一个数 `heap[++size];up(size);`
     *  求集合当中的最小值 `heap[1];`
     *  删除最小值 `heap[1]=heap[size];size--；down(1);`(调换到末尾再删除，因为我们用数组维护堆的话，删头节点很麻烦但是尾节点很方便)
     *  删除任何一个元素 `heap[k]=heap[size];size--;down(k);up(k);`（down和up总会执行一个 省去了判断）
     *  修改任何一个元素`heap[k]=x;down(k);up(k);`

**时间复杂度分析**：求最小值O（1）；插入和删除操作O（logn）；down/up操作O（logn），和树的高度成正比；

**完整代码：**

#include<iostream>
    #include<algorithm>
    using namespace std;
    const int N=100010;
    int n,m;
    int h[N],sizeh;
    void down(int u){ 
        int t=u;//t表示三个点（父节点、左右子节点）里面最小值
        if(u*2<=sizeh &&h[u*2]<h[t])t=u*2;//如果左儿子存在，且小于t，将小的值赋给t
        if(u*2+1<=sizeh &&h[u*2+1]<h[t] )t=u*2+1;
        if(u!=t){ //如果u不是t，那就说明根节点不是最小的，那就和最小的交换一下
            swap(h[u],h[t]);
            down(t);
        }
    }
    void up(int u){ 
        while(u/2 &&h[u/2]>h[u]){ 
            swap(h[u/2],h[u]);
            u/=2;
        }
    }
    int main(){ 
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%d",&h[i]);
        sizeh=n;
        for(int i=n/2;i;i--)down(i);//O(n)建堆,n/2的时候高度是1
        while(m--){ 
            printf("%d ",h[1]);//每次输出当前堆顶元素
            h[1]=h[sizeh];//删掉对顶：讲最后一个元素赋到第一个元素上去
            sizeh--;//数量减少
            down(1);//从上向下维护堆
        }
        return 0;
    }