fork download
copy 
  1. /**
  2.  * Binary Max Heap operations
  3.  * @author Prateek
  4.  *
  5.  */
  6.  class BinaryMaxHeap {
  7.  
  8. 	private int[] heap; //Heap containing Element
  9. 	private int heapSize; // Number of element in the heap
  10.  
  11. 	public BinaryMaxHeap(int size) {
  12. 		this.heap=new int[size];
  13. 		this.heapSize = 0;
  14. 	}
  15.  
  16. 	public boolean isEmpty(){
  17. 		return heapSize == 0;
  18. 	}
  19. 	/**
  20. 	 * Insert Key into Heap
  21. 	 * @param val : key to be inserted in the heap
  22. 	 * @throws HeapException : Incase Heap is full
  23. 	 */
  24. 	public void insert(int val) throws HeapException{
  25. 		if(heapSize  == heap.length)
  26. 			throw new HeapException("Heap Leakage , Overflowing");
  27. 		else{
  28. 			System.out.println("Insert : " +val);
  29. 			heap[++heapSize]=val;
  30. 			swim(heapSize);
  31. 		}
  32. 	}
  33.  
  34. 	private void swim(int index) {
  35. 		while(index > 1 && isLess(index/2, index))
  36. 		{
  37. 			swap(index/2 , index) ;
  38. 			index = index / 2 ;
  39. 		}
  40. 	}
  41.  
  42. 	/**
  43. 	 * @return peek max element of the heap
  44. 	 */
  45. 	public int getMax(){
  46. 		return heap[1];
  47. 	}
  48.  
  49.     /**
  50.      * @return max Element from Heap and remove from heap
  51.      */
  52. 	public int delMax(){
  53. 		int max=heap[1];
  54. 		heap[1] = heap[heapSize--] ;
  55. 		sink(1);
  56. 		return max;
  57. 	}
  58.  
  59.   /**
  60.    * Sink down operation to 
  61.    * @param index : index of the root
  62.    */
  63. 	private void sink(int index) {
  64. 		while(2*index < heapSize) {
  65.  
  66. 			int child= 2*index;  //first child
  67.  
  68. 			if(child < heapSize && isLess(child, child + 1 )) // to pick the higher child
  69. 				child++; //second child
  70.  
  71. 			if(!isLess(index, child)) //break if parent is higher than both children
  72. 				break;
  73.  
  74. 			swap(index , child);
  75. 			index=child;
  76. 		}
  77. 	}
  78.  
  79. 	private void swap(int index1, int index2){
  80. 		int temp = heap[index1];
  81. 		heap[index1] = heap[index2] ;
  82. 		heap[index2] = temp;
  83. 	}
  84.  
  85. 	/**
  86. 	 * @param parentIndex
  87. 	 * @param childIndex
  88. 	 * @return true if parent is smaller than child
  89. 	 */
  90. 	private boolean isLess(int parentIndex , int childIndex){
  91. 		return Integer.compare(heap[parentIndex], heap[childIndex]) < 0 ? true : false; 
  92. 	}
  93.  
  94.  
  95. 	public static void main(String[] args) throws HeapException {
  96. 		BinaryMaxHeap bHeap=new BinaryMaxHeap(10);
  97. 		bHeap.insert(5);
  98. 		bHeap.insert(15);
  99. 		bHeap.insert(3);
  100. 		bHeap.insert(6);
  101. 		bHeap.insert(11);
  102. 		bHeap.insert(2);
  103. 		bHeap.insert(1);
  104. 		bHeap.insert(17);
  105. 		bHeap.insert(18);
  106.  
  107. 		System.out.println("Max Item :" +bHeap.delMax());
  108. 		bHeap.print();
  109.  
  110. 	}
  111.  
  112. 	public void print(){
  113. 		System.out.print("Heap is : ");
  114. 		for(int i=1;i< heap.length ;i++)
  115. 			System.out.print(heap[i] + "\t" );
  116. 	}
  117.  
  118. 	class HeapException extends Exception{
  119. 		public HeapException(String msg) {
  120. 			super(msg);
  121. 		}
  122. 	}
  123. }
  124.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Insert : 5
Insert : 15
Insert : 3
Insert : 6
Insert : 11
Insert : 2
Insert : 1
Insert : 17
Insert : 18
Max Item :18
Heap is : 17	15	3	11	6	2	1	5	11
https://ideone.com/pQm8lZ
language:
Java (12.0.1)
created:
11 years ago
visibility:
secret

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!