题目描述
输入一个长度为n的整数数列,从小到大输出前m小的数。
输入格式
第一行包含整数n和m。
第二行包含n个整数,表示整数数列。
输出格式
共一行,包含m个整数,表示整数数列中前m小的数。
数据范围
1≤m≤n≤105,
1≤数列中元素≤109
输入样例:
5 3
4 5 1 3 2
输出样例:
1 2 3
思路
手写一个小根堆 (小的浮在上面,大的在下面)
1.插入一个数 heap[++size] = x; up(size) 尾部添加,看是不是大数,是向上
2.求集合中当中最小值 heap[1] 小根堆顶部最小
3.删除最小值 swap(heap[1], heap[size)) or heap[1] = heap[size]; size –; down(1)
比如 1 - n + 1 交换1 和 n + 1位置,2 - n保持原小根堆,down(1)即可
4.删除任意一个元素 swap(heap[k], heap[size)) or heap[k] = heap[size]; size –; down(k),up(k)
up down 保证其中一个执行,即这个数可能是大数,也可能是小数,必然执行其中一个
5.修改任意一个元素 heap[k] = x, down(k); up(k);
同理,见上
java
import java.util.Scanner;
public class Main{
static int n, m;
static int N = 100010;
static int[] h = new int[N];
static int size = 0;
// 左右子树
public static void down(int u) {
int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) {
t = u * 2;
}
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) {
t = u * 2 + 1;
}
if (u != t) {
swap(h, u, t);
down(t);
}
}
// 父节点
public static void up(int u) {
while(u/2 > 0 && h[u/2] > h[u]) {
swap(h, u/2, u);
u /= 2;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i = 1; i <= n; i ++) h[i] = sc.nextInt();
size = n;
for(int i = n / 2; i != 0; i --) down(i);
while(m -- > 0){
System.out.print(h[1] + " ");
swap(h, 1, size);
size --;
down(1);
}
}
private static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
python3
N = 100010
h = [0] * N
size = 0
def down(u):
global h, size
t = u
l, r = u * 2, u * 2 + 1
if(l <= size and h[l] < h[t]): t = l
if(r <= size and h[r] < h[t]): t = r
if(u != t):
tmp = h[t]
h[t] = h[u]
h[u] = tmp
down(t)
def up(u):
global h
while(int(u / 2) > 0 and h[u / 2] > h[u]):
swap(h[u / 2], h[u])
u = int(u / 2)
def main():
global h, size
n, m = list(map(int, input().split(" ")))
h = list(map(int, input().split(" ")))
size = n
h.insert(0, 0)
i = int(n / 2)
while(i > 0):
down(i)
i -= 1
while(m):
m -= 1
print(h[1], end=" ")
tmp = h[1]
h[1] = h[size]
h[size] = tmp
size -= 1
down(1)
up(1)
main()
c++
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], s; //堆数组,s堆中元素的个数(从1开始)
void down(int u){
int t = u; //记录当前节点的位置
//小根堆
if(u * 2 <= s && h[u * 2] < h[t]) t = u * 2;
if(u * 2 + 1 <= s && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if(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]);
s = n;
//O(N) 叶子节点n0不需要参与向下排序的操作, n1 + n2需要
// for(int i = n / 2; i != 0; i --) down(i);
for(int i = n / 2; i ; i --) down(i);
while(m --){
printf("%d ", h[1]);
h[1] = h[s]; //头尾交换
s --;
down(1); //中间位置,直接up, down,减少当前值是向上还是向下搜素
up(1); // 这是针对任意元素删除时候做的up操作,这题只需要down(1)即可
}
return 0;
}