第13章二叉树和堆

作者: 得力小泡泡 | 来源:发表于2020-03-31 16:43 被阅读0次

1、任务系统

算法分析

记录下来一个任务的编号，周期和下次提醒时间，放进按提醒时间从小往大排（提醒时间一样按编号从小往大排）的优先队列，循环k次，每次取队首输出，出队，并将其下次提醒时间加上一周期后重新入队。

时间复杂度 $O(nlogn)$

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    static int N = 50010;
    static PriorityQueue<Pair> q = new PriorityQueue<Pair>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int k = Integer.parseInt(s1[1]);
        for(int i = 0;i < n;i ++)
        {
            String[] s2 = br.readLine().split(" ");
            int id = Integer.parseInt(s2[1]);
            int time = Integer.parseInt(s2[2]);
            q.add(new Pair(id,time,time));
        }
        while(k -- > 0)
        {
            Pair t = q.poll();
            System.out.println(t.id);
            q.add(new Pair(t.id,t.time + t.period,t.period));
        }

    }
}
class Pair implements Comparable<Pair>
{
    int id ,time,period;
    Pair(int id,int time,int period)
    {
        this.id = id;
        this.time = time;
        this.period = period;
    }
    @Override
    public int compareTo(Pair o) {
        // TODO 自动生成的方法存根
        if(time == o.time) return Integer.compare(id, o.id);
        return Integer.compare(time, o.time);
    }
    
}

2、n个最小和

算法1

对两个数组分别排序，维护一个数量为n的大根堆，始终维护前n小
枚举a[]元素的过程中，依次从小到大枚举b[]
若大根堆的数量小于n，则加进大根堆中
若大根堆的数量大于等于n，

1、若a[i] + b[i] >= 堆顶元素，则直接break
2、若a[i] + b[i] < 堆顶元素，则大根堆poll出堆顶元素，把a[i] + b[i] 加入到大根堆中

时间复杂度 $O(n^2logn)$

由于有剪枝的存在，所有会比时间复杂度小很多

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;


public class Main {
    static PriorityQueue<Long> q = new PriorityQueue<Long>((x,y) -> y.compareTo(x));
    static int N = 50010;
    static int[] a = new int[N];
    static int[] b = new int[N];
    static long[] ans = new long[N];
    static int k = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] s1 = br.readLine().split(" ");
        for(int i = 0;i < n;i ++) a[i] = Integer.parseInt(s1[i]);
        String[] s2 = br.readLine().split(" ");
        for(int i = 0;i < n;i ++) b[i] = Integer.parseInt(s2[i]);
        Arrays.sort(a,0,n);
        Arrays.sort(b,0,n);
        for(int i = 0;i < n;i ++)
        {
            for(int j = 0;j < n;j ++)
            {
                int x = a[i] + b[j];
                if(q.size() >= n)
                {
                    if(x >= q.peek()) break;
                    q.poll();
                    q.add((long) x);
                }
                else q.add((long) x);
            }
        }
        for(int i = 0;i < n;i ++)
        {
            ans[k ++] = q.poll();
        }
        for(int i = n - 1;i >= 0;i --)
        {
            if(i != 0) System.out.print(ans[i] + " ");
            else System.out.println(ans[i]);
        }
    }
}

算法2

小根堆
先把A数组和B数组从小到大排序，取A数组中的每一个数与B[0]相加，记录取的A的数组下标和B的数组下标和数组中两数之和，放入按和从小到大排的优先队列，每一次取出队首，输出这个和，出队，如果它的B数组下标还没有到最后，就把B的数组下标后移一位，重新计算新的两数之和并入队。

小根堆中共有n个元素，其中每个元素都有a[0],a[1].....a[n - 1]，且唯一，故存储的是a[]数组固定每个元素，搭配b[]数组中的目前可以搭配的最小的元素

证明：由于两个数组从小到大排序，假设a[i]和b[j]是当前优先队列中最小的，由于队列中所有的和始终都有a[]数组的所有元素，则表示a[i]一定是固定的，不需要判断a[i + 1] + b[j]的情况，则把a[i]和b[j + 1]的和添加进去替代a[i]和b[j]即可。

时间复杂度 $O(nlogn)$

Java 代码

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static int N = 50010;
    static int[] a = new int[N];
    static int[] b = new int[N];
    static long[] ans = new long[N];
    static PriorityQueue<Edge> q = new PriorityQueue<Edge>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 0;i < n;i ++) a[i] = scan.nextInt();
        for(int i = 0;i < n;i ++) b[i] = scan.nextInt();
        Arrays.sort(a,0,n);
        Arrays.sort(b,0,n);
        for(int i = 0;i < n;i ++)
        {
            q.add(new Edge(i,0,a[i] + b[0]));
        }
        
        int cnt = 0;
        while(cnt < n)
        {
            Edge t = q.poll();
            ans[cnt ++] = t.sum;
            q.add(new Edge(t.l,t.r + 1,a[t.l] + b[t.r + 1]));
        }
        for(int i = 0;i < n;i ++)
        {
            if(i != n - 1) System.out.print(ans[i] + " ");
            else System.out.print(ans[i]);
        }
    }

}
class Edge implements Comparable<Edge>
{
    int l,r;
    long sum;
    Edge(int l,int r,int sum)
    {
        this.l = l;
        this.r = r;
        this.sum = sum;
    }
    @Override
    public int compareTo(Edge o) {
        // TODO 自动生成的方法存根
        return Long.compare(sum, o.sum);
    }
}

3、银行的客户队列

算法分析

这题主要考察的是以结构体为元素的优先队列的大小根堆的运用
小根堆
PriorityQueue<Pair> s = new PriorityQueue<Pair>();
大根堆
PriorityQueue<Pair> h = new PriorityQueue<Pair>((p1, p2) -> p2.compareTo(p1)) ;

Pair结构体有编号id 和优先级p

1操作：将相应的结构体分别扔进大小根堆
2操作：将大根堆的队头取出并输出id，且把小根堆相应的结构体删除
3操作：将小根堆的队头取出并输出id，且把大根堆相应的结构体删除

时间复杂度 $O(nlogn)$

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;


public class Main {
    static PriorityQueue<Pair> s = new PriorityQueue<Pair>();
    static PriorityQueue<Pair> h = new PriorityQueue<Pair>((p1, p2) -> p2.compareTo(p1)) ;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true)
        {
            String[] s1 = br.readLine().split(" ");
            int op = Integer.parseInt(s1[0]);
            if(op == 0) break;
            if(op == 1)
            {
                int id = Integer.parseInt(s1[1]);
                int p = Integer.parseInt(s1[2]);
                Pair t = new Pair(id,p);
                h.add(t);
                s.add(t);
            }
            
            if(op == 2)
            {
                if(h.isEmpty()) 
                {
                    System.out.println(0);
                    continue;
                }
                
                Pair t = h.poll();
                System.out.println(t.id);
                s.remove(t);
            }
            if(op == 3)
            {
                if(s.isEmpty()) 
                {
                    System.out.println(0);
                    continue;
                }
                
                Pair t = s.poll();
                System.out.println(t.id);
                h.remove(t);
            }
        }
    }
}
class Pair implements Comparable<Pair>
{
    int id,p;
    Pair(int id,int p)
    {
        this.id = id;
        this.p = p;
    }
    @Override
    public int compareTo(Pair o) {
        // TODO 自动生成的方法存根
        return Integer.compare(p, o.p);
    }
}

4、二叉树

算法分析

先把二叉树通过前序和中序构建出来，再交换树中所有节点的左右子节点，就变成一棵镜像树，再用队列层次遍历
1、建二叉树
先通过哈希表记录中序遍历序列的元素在中序遍历中哪个位置
找到前序遍历序列的第一个元素在中序遍历序列的位置y，即绿色区域是y结点值的左子树，蓝色区域是y结点值的右子树

image.png

2、如何变成一棵镜像树
交换树中所有节点的左右子节点，即得到树的镜像。
求一棵树的镜像的过程：先前序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的左右两个子节点，当交换完所有非叶节点的左、右子节点之后，就得到了树的镜像。

时间复杂度 $O(n)$

Java 代码

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N = 35;
    static int[] a = new int[N];
    static int[] b = new int[N];
    static Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    static int[] ans = new int[N];
    static int k = 0;
    //通过前序遍历序列和中序遍历序列建树
    static Node build(int al,int ar,int bl,int br)
    {
        if(al > ar || bl > br) return null;
        int x = a[al];
        int y = map.get(x);
        int len = y - bl;
        Node root = new Node(x);
        root.left = build(al + 1,al + len,bl,y - 1);
        root.right = build(al + len + 1,ar,y + 1,br);
        return root;
    }
    //将二叉树镜像翻转
    static void dfs(Node root)
    {
        if(root == null) return;
        if(root.left == null && root.right == null) return;
        Node temp = root.left;
        root.left = root.right;
        root.right = temp;
        if(root.left != null) dfs(root.left);
        if(root.right != null) dfs(root.right);
    }
    //层次遍历
    static void bfs(Node root)
    {
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        while(!q.isEmpty())
        {
            Node t = q.poll();
            ans[k ++] = t.val;
            if(t.left != null) q.add(t.left);
            if(t.right != null) q.add(t.right);
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 0;i < n;i ++) 
        {
            b[i] = scan.nextInt();
            map.put(b[i], i);
        }
        for(int i = 0;i < n;i ++) a[i] = scan.nextInt();
        Node root = build(0,n - 1,0,n - 1);
        dfs(root);
        
        bfs(root);
        
        for(int i = 0;i < k;i ++)
        {   
            if(i != k - 1) System.out.print(ans[i] + " ");
            else System.out.println(ans[i]);
        }
    }
}
class Node
{
    Node left;
    Node right;
    int val ;
    Node(int val)
    {
        this.val = val;
    }
}

5、n个最小和加强版

先把所有数组排成有序的，先按照第2题 n个最小和 的方式求出第一个数组和第二个数组的前n小，存到t[]数组中，再求出t[]数组和第三个数组的前n小，存到t[]数组中....

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static int N = 1010;
    static long[][] A = new long[N][N];
    static long[] ans = new long[N];
    static PriorityQueue<Edge> q = new PriorityQueue<Edge>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        for(int i = 0;i < m;i ++)
        {
            for(int j = 0;j < n;j ++)
            {
                A[i][j] = scan.nextInt();
            }
            Arrays.sort(A[i],0,n);
        }
        for(int i = 0;i < m - 1;i ++)
        {
            q.clear();
            for(int j = 0;j < n;j ++)
            {
                q.add(new Edge(j,0,A[i][j] + A[i + 1][0]));
            }
            int cnt = 0;
            while(cnt < n)
            {
                Edge t = q.poll();
                ans[cnt ++] = t.sum;
                q.add(new Edge(t.l,t.r + 1,A[i][t.l] + A[i + 1][t.r + 1]));
            }
            for(int j = 0;j < n;j ++) A[i + 1][j] = ans[j];
            
        }
        for(int i = 0;i < n;i ++)
        {
            if(i != n - 1) System.out.print(A[m - 1][i] + " ");
            else System.out.print(A[m - 1][i]);
        }
    }

}
class Edge implements Comparable<Edge>
{
    int l,r;
    long sum;
    Edge(int l,int r,long sum)
    {
        this.l = l;
        this.r = r;
        this.sum = sum;
    }
    @Override
    public int compareTo(Edge o) {
        // TODO 自动生成的方法存根
        return Long.compare(sum, o.sum);
    }
}

第13章二叉树和堆

1、任务系统

算法分析

时间复杂度 $O(nlogn)$

Java代码

2、n个最小和

算法1

时间复杂度 $O(n^2logn)$

Java代码

算法2

时间复杂度 $O(nlogn)$

Java 代码

3、银行的客户队列

算法分析

时间复杂度 $O(nlogn)$

Java代码

4、二叉树

算法分析

时间复杂度 $O(n)$

Java 代码

5、n个最小和加强版

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

第13章 二叉树和堆

1、任务系统

算法分析

时间复杂度

Java代码

2、n个最小和

算法1

时间复杂度

Java代码

算法2

时间复杂度

Java 代码

3、银行的客户队列

算法分析

时间复杂度

Java代码

4、二叉树

算法分析

时间复杂度

Java 代码

5、n个最小和加强版

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

第13章二叉树和堆

时间复杂度 $O(nlogn)$

时间复杂度 $O(n^2logn)$

时间复杂度 $O(nlogn)$

时间复杂度 $O(nlogn)$

时间复杂度 $O(n)$