算法解析
代码有点长,还好逻辑不难,写的时候小心一点就可以了
堆的知识点
一:堆的数据结构
是一个完全二叉树,每个节点分为左节点和右节点,并且左节点小于右节点
索引:当前节点x,左节点 = 2x,右节点 = 2x + 1
又分为了小根堆和大根堆
- 小根堆:每个节点小于等于左右两边的点,
- 大根堆 :父节点的值大于左右子节点的值
二:堆的五种操作
- 插入一个数 heap[++size] = x;up(size);
2:当集合当中的最小值 heap[1];
3:删除最小值 heap[1] = heap[size];size–;down(1);
4:删除任意一个元素 heap[k] = heap[size];size–;up(k);down(k);
5:修改任意一个元素 heap[k] = x;up(k);down(k);
三:堆的用途
- 支持堆排序
- 快速找出集合中的最大值或者最小值
- 构建优先队列
算法题的话跟着下面的流程走一遍,就懂了,注释很详细,不懂问我
Java代码
import java.util.Scanner;
public class Main{
static int N = 100010;
static int[] h = new int[N]; //模拟堆,储存值
static int[] ph = new int[N]; //从位置到堆,以第k次插入为索引,值为下标 ph[k] = size
static int[] hp = new int[N]; //从堆到位置,以下标为索引,值为第几个插入的 hp[size] = k
static int size = 0;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = 0; //m表示第k个插入的
while(n-- > 0)
{
String str = in.next();
if(str.equals("I")){ //插入一个数
int x = in.nextInt();
++size;
++m;
ph[m] = size;
hp[size] = m;
h[size] = x;
up(size);
}
else if(str.equals("PM")) //输出集合中的最小值
{
System.out.println(h[1]);
}
else if(str.equals("DM")) //删除集合中的最小值
{
heap_swap(1,size); //因为要维持映射,所以不能写成h[1] = h[size--];
size--;
down(1);
}
else if(str.equals("D")) //删除第k个插入的数
{
int k = in.nextInt();
k = ph[k];
heap_swap(k,size);
size--;
down(k);
up(k);
}
else if(str.equals("C")) //修改第k个插入的数
{
int k = in.nextInt();
int x = in.nextInt();
k = ph[k]; //找出第k个插入数的索引
h[k] = x;
down(k);
up(k);
}
}
}
private static void down(int u){ //u表示移动前的值的索引,t表示移动后的索引
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)
{
heap_swap(t,u);
down(t);
}
}
private static void up(int u ){
while(u/2 > 0 && h[u] < h[u/2]) //根节点存在 && 当前值小于根节点值
{
heap_swap(u,u/2);
u /= 2; //当前的索引变为根节点的索引
}
}
private static void heap_swap(int a, int b)
{
swap(ph, hp[a], hp[b]); //维护位置到堆的映射
swap(hp, a, b); // 维护堆到位置的映射
swap(h, a, b); // 交换堆中两个元素的值
}
private static void swap(int[] a,int x, int y )
{
int t = a[x];
a[x] = a[y];
a[y] = t;
}
}