【堆】堆排序「堆基础1」

题目

838. 堆排序

---

输入一个长度为 $n$ 的整数数列，从小到大输出前 $m$ 小的数。

输入格式

第一行包含整数 $n$ 和 $m$。

第二行包含 $n$ 个整数，表示整数数列。

输出格式

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

数据范围

$1 \le m \le n \le 10^5$，
$1 \le 数列中元素 \le 10^9$

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

解题

方法一：堆

思路

堆模版：堆

堆

堆是一棵完全二叉树，最大堆（大根堆）是指任意节点上的值都不小于其子节点值的堆，最小堆（小根堆）是指任意节点上的值都不大于其子节点值的堆。

我们会使用一个一维数组来存储堆，根节点的下标为 $1$，节点 $x$ 的左子节点下标为 $2x$ 右子节点下标是 $2x + 1$。堆有两个操作：

• down(int k) 表示把节点 k 向下调整：
  • 从节点 k ，节点 k 的左子节点，节点 k 的右子节点这三个节点中找到最小的节点(min)。
  • 如果最小节点是 k，那它就不需要调整。
  • 否则把 min 与节点 k 进行交换，然后把 min 当作新的要调整的节点递归地向下调整。
• up(int k) 表示把节点 k 向上调整：
  • 循环比较节点 k 与其根节点，如果节点 k 小于其根节点就交换并继续循环，否则推出循环。

以上的两个操作组合起来就可以延伸为堆常用的五个操作：

1. 插入一个数 x：heap[++size] = x; up(size);
2. 求最小值：heap[1]
3. 删除最小值：heap[1] = heap[size]; --size; down(1);
4. 删除任一元素 k：heap[k] = heap[size]; --size; down(k); up(k);
5. 修改任一元素 k 为 x：heap[k] = x; down(k); up(k);

本题只需要用到求最小值与删除最小值的操作，所以只用写 down 操作。

输入的数存入数组后是无序的，每次向堆中插入值所需的时间复杂度是 $O(logN)$，总共就需要 $O(NlogN)$ 的时间用于建堆，但是 for (int i = n / 2; i > 0; --i) down(i); 可以以 $O(N)$ 的时间复杂度把一个无序数组建成堆。

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int heap[N], idx;
int n, m;

void down(int k) {
    int min = k;
    if (k * 2 <= idx && heap[k * 2] < heap[min]) min = k * 2;
    if (k * 2 + 1 <= idx && heap[k * 2 + 1] < heap[min]) min = k * 2 + 1;
    if (min != k) {
        swap(heap[min], heap[k]);
        down(min);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    idx = n;
    for (int i = 1; i <= n; ++i) scanf("%d", &heap[i]);
    for (int i = n / 2; i > 0; --i) down(i);
    while (m--) {
        printf("%d ", heap[1]);
        heap[1] = heap[idx--];
        down(1);
    }
    
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static int[] heap;
    static int size;
    
    static void down(int k) {
        int min = k;
        if (k * 2 <= size && heap[k * 2] < heap[min]) min = k * 2;
        if (k * 2 + 1 <= size && heap[k * 2 + 1] < heap[min]) min = k * 2 + 1;
        if (min != k) {
            int tmp = heap[min];
            heap[min] = heap[k];
            heap[k] = tmp;
            down(min);
        }
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        size = n;
        heap = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            heap[i] = (int) in.nval;
        }
        for (int i = n / 2; i >= 1; --i) down(i);
        while (m-- > 0) {
            System.out.print(heap[1] + " ");
            heap[1] = heap[size--];
            down(1);
        }
    }
}