fork(2) download
copy 
  1. class BinaryHeap {
  2.  
  3. 	private int nodes[];
  4. 	private int size;
  5. 	private int capacity;
  6.  
  7.  
  8. 	public BinaryHeap(int capacity) {
  9. 		this.size = 0;
  10. 		this.capacity = capacity;
  11. 		this.nodes = new int[capacity + 1];
  12. 	}
  13.  
  14. 	public int size() {
  15. 		return size;
  16. 	}
  17.  
  18. 	public int findMin() {
  19. 		if (size <= 0) {
  20. 			throw new RuntimeException("Empty Heap is empty.");
  21. 		}
  22. 		return nodes[1];
  23. 	}
  24.  
  25. 	public void insert(int e) {
  26. 		if (size >= capacity) {
  27. 			throw new RuntimeException("Heap overflow.");
  28. 		}
  29.  
  30. 		size++;
  31. 		nodes[size] = e;
  32. 		percolateUp();
  33. 	}
  34.  
  35. 	public int deleteMin() {
  36. 		if (size <= 0) {
  37. 			throw new RuntimeException("Empty Heap is empty.");
  38. 		}
  39. 		int min = findMin();
  40. 		nodes[1] = nodes[size];
  41. 		size--;
  42. 		percolateDown();
  43. 		return min;
  44. 	}
  45.  
  46. 	private void percolateDown() {
  47. 		int index = 1;
  48. 		while (true) {
  49. 			int child = index * 2;
  50. 			if (child > size)
  51. 				break;
  52. 			if (child + 1 <= size) {
  53. 				// if there are two children -> take the smallest or
  54. 				// if they are equal take the left one
  55. 				child = findMin(child, child + 1);
  56. 			}
  57. 			if (nodes[index] <= nodes[child])
  58. 				break;
  59. 			swap(index, child);
  60. 			index = child;
  61. 		}
  62. 	}
  63.  
  64. 	private void percolateUp() {
  65. 		int index = size();
  66. 		while (index > 1) {
  67. 			int parent = index / 2;
  68. 			if (nodes[index] >= nodes[parent])
  69. 				break;
  70. 			swap(index, parent);
  71. 			index = parent;
  72. 		}
  73. 	}
  74.  
  75. 	private void swap(int i, int j) {
  76. 		int temp = nodes[i];
  77. 		nodes[i] = nodes[j];
  78. 		nodes[j] = temp;
  79. 	}
  80.  
  81. 	private int findMin(int leftChild, int rightChild) {
  82. 		if (nodes[leftChild] <= nodes[rightChild]) {
  83. 			return leftChild;
  84. 		} else {
  85. 			return rightChild;
  86. 		}
  87. 	}
  88.  
  89. 	public static void main(String[] args) {
  90. 		BinaryHeap bh = new BinaryHeap(10);
  91. 		bh.insert(7);
  92. 		bh.insert(5);
  93. 		bh.insert(9);
  94. 		bh.insert(6);
  95. 		bh.insert(4);
  96. 		bh.insert(8);
  97. 		bh.insert(10);
  98. 		bh.insert(1);
  99. 		bh.insert(3);
  100. 		bh.insert(2);
  101.  
  102. 		System.out.println("Size of Binary Heap is : " + bh.size());
  103.  
  104. 		System.out.println("Delete min from Binary Heap : " + bh.deleteMin());
  105. 		System.out.println("Size of Binary Heap is : " + bh.size());
  106.  
  107. 		System.out.println("Delete min from Binary Heap : " + bh.deleteMin());
  108. 		System.out.println("Size of Binary Heap is : " + bh.size());
  109. 	}
  110.  
  111. }
Success #stdin #stdout 0.06s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Size of Binary Heap is : 10
Delete min from Binary Heap : 1
Size of Binary Heap is : 9
Delete min from Binary Heap : 2
Size of Binary Heap is : 8
https://ideone.com/FnSiPv
language:
Java (12.0.1)
created:
9 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!