如何手写一个堆
- 1、插入一个数
- 2、求集合当中的最小值
- 3、删除最小值
- 4、删除任意一个元素
- 5、修改任意一个元素
1、heap[size ++] = x;
2、求集合当中最小值
return heap[1]
3、删除最小值
heap[1] = heap[size];
size --;
down(1);
4、删除任意一个元素
heap[k] = heap[size];
size --;
变小的话：up(k)；
变大的话 ：down(k);
或者 直接down(k)， up(k)； 肯定只会执行一次
5、修改任意一个元素
heap[k] = x;
down(k);
up(k);
只会执行一次
堆排序
只用到了取最小值，以及删除最小值，所以只实现down 就ok了；
import java.util.*;
public class Main{
static int N = 100010;
static int []h = new int [N];
static int n, m;
static void down(int u){
int t = u;
if(u * 2 <= n && h[u * 2] < h[t]) t = u * 2;
if(u * 2 + 1 <= n && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if(t != u){
int swap = h[u];
h[u] = h[t];
h[t] = swap;
down(t);
}
}
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();
//建堆的方式；
for(int i = n / 2; i > 0; i --) down(i);
while( m -- > 0){
System.out.print(h[1] + " ");
h[1] = h[n --];
down(1);
}
}
}
