SHARE
TWEET

Untitled

a guest Oct 15th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Scanner;
  2.  
  3. public class Heap {
  4.  
  5.     public static int len;
  6.  
  7.     public static int extract(int[] h) {
  8.         int tmp = h[0];
  9.         h[0] = h[len - 1];
  10.         h[len - 1] = tmp;
  11.         len--;
  12.         int i = 0;
  13.         int j;
  14.         while (true) {
  15.             j = i;
  16.             if ((2 * i + 1) < len && h[2 * i + 1] > h [j]) {
  17.                 j = 2 * i + 1;
  18.             }
  19.             if ((2 * i + 2) < len && h[2 * i + 2] > h [j]) {
  20.                 j = 2 * i + 2;
  21.             }
  22.             if (j == i) {
  23.                 break;
  24.             }
  25.             i = j;
  26.         }
  27.         return h[len];
  28.     }
  29.  
  30.     public static int[] insert(int[] h, int x) {
  31.         len++;
  32.         h[len - 1] = x;
  33.         int i = len - 1;
  34.         int tmp;
  35.         while (i > 0 && h[i] > h[(i - 1) / 2]) {
  36.             tmp = h[i];
  37.             h[i] = h[(i - 1) / 2];
  38.             h[(i - 1) / 2] = tmp;
  39.             i = (i - 1) / 2;
  40.         }
  41.         return h;
  42.     }
  43.     public static void main(String[] args) {
  44.         Scanner sc = new Scanner(System.in);
  45.         int n = sc.nextInt();
  46.         int x, res;
  47.         len = 0;
  48.         int[] h = new int[100001];
  49.         for (int i = 0; i < n; i++) {
  50.             if (sc.nextInt() == 0) {
  51.                 x = sc.nextInt();
  52.                 insert(h,x);
  53.             } else {
  54.                 res = extract(h);
  55.                 System.out.println(res);
  56.             }
  57.         }
  58.     }
  59. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top