fork(1) 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. 	static class MyHeap<T extends Comparable<T>> {
  11. 		final ArrayList<T> data;
  12. 		final int n;
  13. 		int used;
  14.  
  15. 		public MyHeap(int n) {
  16. 			this.n = n;
  17. 			this.data = new ArrayList<>(n);
  18. 		}
  19.  
  20. 		public void add(T elem) {
  21. 			if (used == n)
  22. 				throw new RuntimeException("heap full");
  23. 			if (data.size() < n)
  24. 				data.add(elem);
  25. 			else
  26. 				data.set(used, elem);
  27. 			used ++;
  28. 			bubbleUp(used - 1);
  29. 		}
  30.  
  31. 		protected void bubbleUp(int pos) {
  32. 			while (pos > 0) {
  33. 				int parent = (pos - 1) / 2;
  34. 				if (data.get(parent).compareTo(data.get(pos)) < 0)
  35. 					return;
  36. 				T temp = data.get(parent);
  37. 				data.set(parent, data.get(pos));
  38. 				data.set(pos, temp);
  39. 			}
  40. 		}
  41.  
  42. 		protected void bubbleDown(int pos) {
  43. 			while (2 * pos + 1 < used) {
  44. 				int path = 2 * pos + 1;
  45. 				int child2 = 2 * pos + 2;
  46. 				if (child2 < used && data.get(child2).compareTo(data.get(path)) < 0)
  47. 					path = child2;
  48. 				if (data.get(pos).compareTo(data.get(path)) > 0) {
  49. 					T temp = data.get(pos);
  50. 					data.set(pos, data.get(path));
  51. 					data.set(path, temp);
  52. 					pos = path;
  53. 				}
  54. 			}
  55. 		}
  56.  
  57. 		public T pop() {
  58. 			if (used == 0) return null;
  59. 			T res = data.get(0);
  60. 			data.set(0, data.get(used));
  61. 			used --;
  62. 			bubbleDown(0);
  63. 			return res;
  64. 		}
  65.  
  66. 		public int size() {
  67. 			return used;
  68. 		}
  69.  
  70. 	}
  71.  
  72. 	public static void main (String[] args) throws java.lang.Exception
  73. 	{
  74. 		MyHeap<Integer> heap = new MyHeap<>(10);
  75. 		heap.add(15);
  76. 		heap.add(324);
  77. 		heap.add(-2);
  78. 		heap.add(22);
  79. 		heap.add(65);
  80. 		heap.add(11);
  81. 		heap.add(19);
  82.  
  83. 		while (heap.size() > 0) {
  84. 			int a = heap.pop();
  85. 			System.out.println(a);
  86. 		}
  87. 	}
  88. }
Runtime error #stdin #stdout #stderr 0.11s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 7, Size: 7
	at java.util.ArrayList.rangeCheck(ArrayList.java:653)
	at java.util.ArrayList.get(ArrayList.java:429)
	at Ideone$MyHeap.pop(Main.java:60)
	at Ideone.main(Main.java:84)
https://ideone.com/jIzTho
language:
Java (HotSpot 12)
created:
7 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!