README.md

堆排序

堆排序算法模板：

// h存储堆中的值，h[1]是堆顶，h[x]的左儿子是2x，右儿子是2x+1int[] h = newint[N]; // 向下调整voiddown(intu) { intt = 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 (t != u) { swap(t, u); down(t); } } // 向上调整voidup(intu) { while (u / 2 > 0 && h[u / 2] > h[u]) { swap(u / 2, u); u /= 2; } } // O(n) 建堆for (inti = n / 2; i > 0; --i) { down(i); }

题目描述

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

输入格式

第一行包含整数 n 和 m。

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

输出格式

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

数据范围

• 1 ≤ m ≤ n ≤ 10^5
• 1 ≤ 数列中元素 ≤ 10^9

输入样例：

5 3 4 5 1 3 2 

输出样例：

1 2 3 

代码实现

Python3

n, m=list(map(int, input().split(" "))) h= [0] +list(map(int, input().split(" "))) size=ndefdown(u): t=uifu*2<=sizeandh[u*2] <h[t]: t=u*2ifu*2+1<=sizeandh[u*2+1] <h[t]: t=u*2+1ift!=u: h[t], h[u] =h[u], h[t] down(t) defup(u): whileu//2>0andh[u//2] >h[u]: h[u//2], h[u] =h[u], h[u//2] u//=2foriinrange(n//2, 0, -1): down(i) res= [] foriinrange(m): res.append(h[1]) h[1] =h[size] size-=1down(1) print(' '.join(list(map(str, res))))

Java

importjava.util.Scanner; publicclassMain { privatestaticint[] h = newint[100010]; privatestaticintsize; publicstaticvoidmain(String[] args) { Scannersc = newScanner(System.in); intn = sc.nextInt(), m = sc.nextInt(); for (inti = 1; i <= n; ++i) { h[i] = sc.nextInt(); } size = n; for (inti = n / 2; i > 0; --i) { down(i); } while (m-- > 0) { System.out.print(h[1] + " "); h[1] = h[size--]; down(1); } } publicstaticvoiddown(intu) { intt = 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 (t != u) { swap(t, u); down(t); } } publicstaticvoidup(intu) { while (u / 2 > 0 && h[u / 2] > h[u]) { swap(u / 2, u); u /= 2; } } publicstaticvoidswap(inti, intj) { intt = h[i]; h[i] = h[j]; h[j] = t; } }

Rust

use std::io;fnheap_sort(nums:&mutVec<i32>){let n = nums.len();for i in(0..n / 2).rev(){sink(nums, i, n);}for i in(1..n).rev(){let temp = nums[0]; nums[0] = nums[i]; nums[i] = temp;sink(nums,0, i);}}fnsink(nums:&mutVec<i32>,muti:usize,n:usize){loop{let left = i *2 + 1;let right = left + 1;letmut largest = i;if left < n && nums[left] > nums[largest]{ largest = left;}if right < n && nums[right] > nums[largest]{ largest = right;}if largest == i {break;}let temp = nums[i]; nums[i] = nums[largest]; nums[largest] = temp; i = largest;}}fnmain() -> io::Result<()>{letmut s = String::new(); io::stdin().read_line(&mut s)?;let s:Vec<usize> = s.split(' ').map(|s| s.trim().parse().unwrap()).collect();// let n = s[0];let m = s[1];letmut nums = String::new(); io::stdin().read_line(&mut nums)?;letmut nums:Vec<i32> = nums.split(' ').map(|s| s.trim().parse().unwrap()).collect();heap_sort(&mut nums);for num in nums.iter().take(m){print!("{} ", num);}Ok(())}

Go

package main import"fmt"constN=100010var ( sizeinth []int ) funcup(uint) { foru/2!=0&&h[u/2] >h[u] { //父节点比当前结点小h[u/2], h[u] =h[u], h[u/2] //交换u/=2 } } funcdown(uint) { t:=u//t 最小值ifu*2<=size&&h[2*u] <h[t] { //左孩子存在且小于tt=u*2 } ifu*2+1<=size&&h[2*u+1] <h[t] { //右孩子存在且小于tt=2*u+1 } ifu!=t { h[u], h[t] =h[t], h[u] down(t) //递归处理 } } funcmain() { varn, minth=make([]int, N) fmt.Scanf("%d%d", &n, &m) //创建一维数组1fori:=1; i<=n; i++ { fmt.Scanf("%d", &h[i]) } size=n// 一维数组变为小根堆fori:=n/2; i!=0; i-- { down(i) } for ; m!=0; m-- { fmt.Printf("%d ", h[1]) h[1] =h[size] size--down(1) } }

解法

方法一

Python3

n, m=list(map(int, input().split(" "))) h= [0] +list(map(int, input().split(" "))) size=ndefdown(u): t=uifu*2<=sizeandh[u*2] <h[t]: t=u*2ifu*2+1<=sizeandh[u*2+1] <h[t]: t=u*2+1ift!=u: h[t], h[u] =h[u], h[t] down(t) defup(u): whileu//2>0andh[u//2] >h[u]: h[u//2], h[u] =h[u], h[u//2] u//=2foriinrange(n//2, 0, -1): down(i) res= [] foriinrange(m): res.append(h[1]) h[1] =h[size] size-=1down(1) print(' '.join(list(map(str, res))))

Java

importjava.util.Scanner; publicclassMain { privatestaticint[] h = newint[100010]; privatestaticintsize; publicstaticvoidmain(String[] args) { Scannersc = newScanner(System.in); intn = sc.nextInt(), m = sc.nextInt(); for (inti = 1; i <= n; ++i) { h[i] = sc.nextInt(); } size = n; for (inti = n / 2; i > 0; --i) { down(i); } while (m-- > 0) { System.out.print(h[1] + " "); h[1] = h[size--]; down(1); } } publicstaticvoiddown(intu) { intt = 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 (t != u) { swap(t, u); down(t); } } publicstaticvoidup(intu) { while (u / 2 > 0 && h[u / 2] > h[u]) { swap(u / 2, u); u /= 2; } } publicstaticvoidswap(inti, intj) { intt = h[i]; h[i] = h[j]; h[j] = t; } }

Go

package main import"fmt"constN=100010var ( sizeinth []int ) funcup(uint) { foru/2!=0&&h[u/2] >h[u] { //父节点比当前结点小h[u/2], h[u] =h[u], h[u/2] //交换u/=2 } } funcdown(uint) { t:=u//t 最小值ifu*2<=size&&h[2*u] <h[t] { //左孩子存在且小于tt=u*2 } ifu*2+1<=size&&h[2*u+1] <h[t] { //右孩子存在且小于tt=2*u+1 } ifu!=t { h[u], h[t] =h[t], h[u] down(t) //递归处理 } } funcmain() { varn, minth=make([]int, N) fmt.Scanf("%d%d", &n, &m) //创建一维数组1fori:=1; i<=n; i++ { fmt.Scanf("%d", &h[i]) } size=n// 一维数组变为小根堆fori:=n/2; i!=0; i-- { down(i) } for ; m!=0; m-- { fmt.Printf("%d ", h[1]) h[1] =h[size] size--down(1) } }

Rust

use std::io;fnheap_sort(nums:&mutVec<i32>){let n = nums.len();for i in(0..n / 2).rev(){sink(nums, i, n);}for i in(1..n).rev(){let temp = nums[0]; nums[0] = nums[i]; nums[i] = temp;sink(nums,0, i);}}fnsink(nums:&mutVec<i32>,muti:usize,n:usize){loop{let left = i *2 + 1;let right = left + 1;letmut largest = i;if left < n && nums[left] > nums[largest]{ largest = left;}if right < n && nums[right] > nums[largest]{ largest = right;}if largest == i {break;}let temp = nums[i]; nums[i] = nums[largest]; nums[largest] = temp; i = largest;}}fnmain() -> io::Result<()>{letmut s = String::new(); io::stdin().read_line(&mut s)?;let s:Vec<usize> = s.split(' ').map(|s| s.trim().parse().unwrap()).collect();// let n = s[0];let m = s[1];letmut nums = String::new(); io::stdin().read_line(&mut nums)?;letmut nums:Vec<i32> = nums.split(' ').map(|s| s.trim().parse().unwrap()).collect();heap_sort(&mut nums);for num in nums.iter().take(m){print!("{} ", num);}Ok(())}