10-堆

算法思想

堆

• 堆是满足一些条件的完全二叉树

算法模板

import java.util.*;
public class Main {
    static int N = 100010;
    static int[] h = new int[N],    
    // hp[i](heap -> point)存储堆中第 i 元素的插入序号（第 k 个插入）
    // hp 记录每个元素的插入序号
    hp = new int[N],
    // ph[i](point -> heap)存储第 i 个插入的元素在堆中的索引
    ph = new int[N];
    // 为什么有了 hp 还需要 ph
    // 便于根据插入序号（k）查找堆中对应元素，否则需要遍历整个堆
    
    // cnt 代表堆中元素的总数
    // m 代表最小的未使用的插入序号（从1开始）
    static int cnt, m;


    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        while(n -- > 0)
        {
            String s = in.next();
            int k, x;
            if(s.equals("I"))
            {
                x = in.nextInt();
                m ++;
                cnt ++;
                ph[m] = cnt;
                hp[cnt] = m;

                h[cnt] = x;
                up(cnt);
            }
            else if(s.equals("PM"))
            {
                System.out.println(h[1]);
            }
            else if(s.equals("DM"))
            {
                heap_swap(1, cnt);
                cnt --;
                down(1);
            }
            else if(s.equals("D"))
            {
                k = in.nextInt();
                int index = ph[k];

                heap_swap(index, cnt);
                cnt --;
                // 堆中的任一元素的值发生变化后,
                // 可能需要上移或下坠。
                // 此处调用直接调用两个方法，
                // 但是只会执行其中一个方法，
                // 另一个方法会因为条件不满足而直接退出
                up(index);
                down(index);
            }            
            else if(s.equals("C"))
            {
                k = in.nextInt();
                x = in.nextInt();
                // 第 k 个插入的元素在堆中的索引
                int index = ph[k];

                h[index] = x;
                up(index);
                down(index);
            }
        }
    }

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

    static void down(int u)
    {
        int t = u;
        if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
        if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
        if(t != u)
        {
            heap_swap(t, u);
            down(t);
        }
    }

    // 堆中元素的索引 i, j
    static void heap_swap(int i, int j)
    {   // 堆中元素的插入序号
        int k1 = hp[i], k2 = hp[j];

        swap(ph, k1, k2);
        swap(hp, i, j);
        swap(h, i, j);
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}