fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) {
  11. 		Random rand = new Random(System.nanoTime());
  12. 		int N = rand.nextInt(20) + 10;
  13. 		int[][] arr = new int[N][];
  14. 		for (int i = 0; i < N; i++) {
  15. 		    int m = rand.nextInt(10) + 5;
  16. 		    if (i % 2 != m % 2) m++;
  17. 		    arr[i] = new int[m];
  18. 		    for (int j = 0; j < m; j++) {
  19. 		        arr[i][j] = rand.nextInt(100);
  20. 		    }
  21. 		    Arrays.sort(arr[i]);
  22. 		}
  23. 		int P = 4;
  24. 		int[][] ps = new int[P][];
  25. 		int size = 0;
  26. 		for (int i = 0; i < P; i++) {
  27. 		    ps[i] = arr[rand.nextInt(arr.length)];
  28. 		    size += ps[i].length;
  29. 		    System.out.print("[");
  30. 		    for (int p : ps[i]) {
  31. 		        System.out.printf("%d, ", p);
  32. 		    }
  33. 		    System.out.print("], ");
  34. 		}
  35. 		System.out.println();
  36. 		Heap heap = new Heap(P);
  37. 		for (int i = 0; i < P; i++) {
  38. 		    heap.push(ps[i]);
  39. 		}
  40. 		do {
  41. 		    System.out.printf("%d, ", heap.peek());
  42. 		} while (heap.pop());
  43. 		System.out.println();
  44. 		int[] es = new int[size];
  45. 		for (int i = 0, j = 0; i < P; i++) {
  46. 		    for (int p : ps[i]) {
  47. 		        es[j] = p;
  48. 		        j++;
  49. 		    }
  50. 		}
  51. 		Arrays.sort(es);
  52. 		for (int e : es) {
  53. 		    System.out.printf("%d, ", e);
  54. 		}
  55. 		System.out.println();
  56. 	}
  57. 	static class Slice {
  58. 	    int[] ref;
  59. 	    int index, endIndex;
  60. 	    Slice(int[] r) {
  61. 	        ref = r; index = 0; endIndex = r.length;
  62. 	    }
  63. 	    int len() { return endIndex - index; }
  64. 	    int get() { return ref[index]; }
  65. 	    boolean next() { index++; return index < endIndex; }
  66. 	}
  67. 	static class Heap {
  68. 	    Slice[] buf;
  69. 	    int index = 0;
  70. 	    Heap(int len) {
  71.             buf = new Slice[len];
  72. 	    }
  73. 	    void push(int[] arr) {
  74. 	        buf[index] = new Slice(arr);
  75. 	        up(index);
  76. 	        index++;
  77. 	    }
  78. 	    int peek() {
  79. 	        return buf[0].get();
  80. 	    }
  81. 	    boolean pop() {
  82. 	        if (!buf[0].next()) {
  83. 	            buf[0] = buf[index-1];
  84. 	            buf[index-1] = null;
  85. 	            index--;
  86. 	            if (index == 0) return false;
  87. 	        }
  88.             down(0);
  89.             return true;
  90. 	    }
  91. 	    void swap(int i, int j) {
  92. 	        Slice tmp = buf[i];
  93. 	        buf[i] = buf[j]; buf[j] = tmp;
  94. 	    }
  95. 	    void up(int i) {
  96. 	        if (i == 0) { down(0); return; }
  97. 	        int j = (i - 1) >> 1;
  98. 	        if (buf[i].get() < buf[j].get()) {
  99. 	            swap(i, j); up(j);
  100. 	        } else {
  101. 	            down(i);
  102. 	        }
  103. 	    }
  104. 	    void down(int i) {
  105. 	        int k = (i + 1) << 1;
  106. 	        int j = k - 1;
  107. 	        if (j >= buf.length) return;
  108. 	        if (buf[j] == null) return;
  109. 	        if (k < buf.length && buf[k] != null) {
  110. 	            if (buf[j].get() < buf[k].get()) {
  111. 	                if (buf[j].get() < buf[i].get()) {
  112. 	                    swap(j, i); down(j);
  113. 	                }
  114. 	            } else if (buf[k].get() < buf[i].get()) {
  115. 	                swap(k, i); down(k);
  116. 	            }
  117. 	        } else if (buf[j].get() < buf[i].get()) {
  118.                 swap(j, i); down(j);
  119. 	        }
  120. 	    }
  121. 	}
  122. }
Success #stdin #stdout 0.07s 2184192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[0, 0, 6, 35, 41, 63, 64, 73, 86, 86, ], [18, 20, 34, 39, 51, 53, 55, 57, 59, 66, 79, 83, 92, ], [18, 20, 34, 39, 51, 53, 55, 57, 59, 66, 79, 83, 92, ], [5, 23, 28, 28, 30, 33, 36, 43, 46, 80, 90, 98, ], 
0, 0, 5, 6, 18, 18, 20, 20, 23, 28, 28, 30, 33, 34, 34, 35, 36, 39, 39, 41, 43, 46, 51, 51, 53, 53, 55, 55, 57, 57, 59, 59, 63, 64, 66, 66, 73, 79, 79, 80, 83, 83, 86, 86, 90, 92, 92, 98, 
0, 0, 5, 6, 18, 18, 20, 20, 23, 28, 28, 30, 33, 34, 34, 35, 36, 39, 39, 41, 43, 46, 51, 51, 53, 53, 55, 55, 57, 57, 59, 59, 63, 64, 66, 66, 73, 79, 79, 80, 83, 83, 86, 86, 90, 92, 92, 98,
https://ideone.com/bCYNyn
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!