堆 | 东川

堆

堆？

二叉树（完全二叉树）

小根堆：每个点小于等于左右儿子，所以最小值就是根节点

具体：一维数组存储一个二叉树

堆的操作：

插入一个数插到最后一个元素 heap[++size] = x; up(size)
求集合中的最小值 heap[1]
删除最小值 heap[1] = heap[size]; siez–; down(1);
删除任意一个元素 heap[k] = heap[size]; size–; down(k);up(k);
修改任意一个元素

堆在代码中的两个基本操作：down和up，调整

down操作，莫一个点的值变大了，就要往下沉

三个点中的最小值，交换

up，某个点变小了，往上

堆的初始化

模板

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

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)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);


//java代码几个关键的
 public static void down(int i){
        int min = i;
        int l = 2*i;
        int r = 2*i+1;
        if(l<=n && heap[l]<heap[min]){
            min = l;
        }
        if(r <=n && heap[r]<heap[min]){
			min = r;
		}
        
        if(min!=i){
            int temp = heap[min];
			heap[min] = heap[i];
			heap[i] = temp;
			//记得递归down
			down(min);
        }
 }

//初始化
for(int i=n/2;i>0;i--){
    down(i);
}

题目

AcWing

838 堆排序
839 模拟堆

Ac839 堆排序

描述

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

解答

import java.io.*;

public class Main {
	static final int N = 100010;
	static int[] heap = new int[N];
	static int n;
    
    public static void down(int i){
        int min = i;
        int l = 2*i;
        int r = 2*i+1;
        if(l<=n && heap[l]<heap[min]){
            min = l;
        }
        if(r <=n && heap[r]<heap[min]){
			min = r;
		}
        
        if(min!=i){
            int temp = heap[min];
			heap[min] = heap[i];
			heap[i] = temp;
			//记得递归down
			down(min);
        }
        
        
    }
    
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] line = br.readLine().split(" ");
		n = Integer.parseInt(line[0]); //n个整数
		int m = Integer.parseInt(line[1]);//m个数
        
        String[] Strarr = br.readLine().split(" ");
		for(int i = 1;i<=n;i++){
			heap[i] = Integer.parseInt(Strarr[i-1]);
		}
        
        //堆的初始化
        for(int i=n/2;i>0;i--){
            down(i);
        }
        
        //输出
        for(int i=1;i<=m;i++){
			System.out.print(heap[1]+" ");
			heap[1] = heap[n--]; //很关键
			down(1);
			
		}
    
    }
    
    
    
    
}

Ac839 模拟堆

描述

维护一个集合，初始时集合为空，支持如下几种操作：

“I x”，插入一个数x；

“PM”，输出当前集合中的最小值；

“DM”，删除当前集合中的最小值（数据保证此时的最小值唯一）；

“D k”，删除第k个插入的数；

“C k x”，修改第k个插入的数，将其变为x；

我们要知道第k个插入点在哪里

分析：插入第k个数，多开两个额外数组ph和hp

ph 第k个点在堆内

hp 堆的点是第k个?

解答

import java.io.*;

public class Main {
    
    static final int N = 100010;
    static int[] heap = new int[N];
    static int size;

    static int[] ph=new int[N];
    static int[] hp=new int[N];
    static int idx;
    
    //交换值
    static void swap(int[] arr, int a, int b){
        int tmp=arr[a];
        arr[a]=arr[b];
        arr[b]=tmp;
    }
    
    //交换ph，和hp,交换值
    static void heap_swap(int a, int b){
        //ph 指到树上
        swap(ph, hp[a], hp[b]);
        swap(hp, a, b);
        swap(heap, a, b);
    }
    
    static void down(int i){
        int min=i;
        int l=i*2; int r=i*2+1;
        if(l<=size&&heap[l]<heap[t]) min=l;
        if(r<=size&&heap[r]<heap[t]) min=r;

        if(min!=i){
            heap_swap(min,i);
            down(min);
        }
    }
    
    public static void up(int i){
        while(i/2>0 && heap[i/2]>heap[i]){
            heap_swap(i, i/2);
            i /= 2;
        }
    }
	public static void main(String[] args) throws Exception {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			int n = Integer.parseInt(br.readLine());
			
			while(n-->0){
				String[] line = br.readLine().split(" ");
				String op = line[0];
				
				if(op.equals("I")){
					int x = Integer.parseInt(line[1]);
					heap[++size]=x;
					ph[++idx] = size;
					hp[size]=idx;
					up(size);
				}else if(op.equals("DM")){
					heap_swap(1, size);
					size--;
					down(1);
				}else if(op.equals("D")){
					int k = Integer.parseInt(line[1]);
					int cur = ph[k];
					
					heap_swap(cur, size);
					size--;
					down(cur);up(cur);
				}else if(op.equals("PM")){
					System.out.println(heap[1]);
				}else{
					int k = Integer.parseInt(line[1]);
					int x = Integer.parseInt(line[2]);
					int cur = ph[k];
					
					heap[cur]=x;
					down(cur);up(cur);
				}
			}
			
					
		}		  
    
}