侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-11-10 / 0 评论 / 0 点赞 / 31 阅读 / 962 字 / 正在检测是否收录...

题目

838. 堆排序


输入一个长度为 nn 的整数数列,从小到大输出前 mm 小的数。

输入格式

第一行包含整数 nnmm

第二行包含 nn 个整数,表示整数数列。

输出格式

共一行,包含 mm 个整数,表示整数数列中前 mm 小的数。

数据范围

1mn1051 \le m \le n \le 10^5
1数列中元素1091 \le 数列中元素 \le 10^9

输入样例:

5 3
4 5 1 3 2

输出样例:

1 2 3

解题

方法一:堆

思路

堆模版:

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

我们会使用一个一维数组来存储堆,根节点的下标为 11,节点 xx 的左子节点下标为 2x2x 右子节点下标是 2x+12x + 1。堆有两个操作:

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

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

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

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

输入的数存入数组后是无序的,每次向堆中插入值所需的时间复杂度是 O(logN)O(logN),总共就需要 O(NlogN)O(NlogN) 的时间用于建堆,但是 for (int i = n / 2; i > 0; --i) down(i); 可以以 O(N)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);
        }
    }
}

0

评论区