Guest User

Untitled

a guest
Nov 18th, 2017
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.25 KB | None | 0 0
  1. import java.util.HashMap;
  2. import java.util.Scanner;
  3.  
  4. public class QHEAP1 {
  5. private static int count = 1;
  6. private static MinimumHeap<Integer> root = null;
  7. HashMap<Integer,Integer> h = new HashMap<>();
  8. public static void main(String args[]) {
  9. long startTime = System.currentTimeMillis();
  10. Scanner sc = new Scanner(System.in);
  11. QHEAP1 q = new QHEAP1();
  12. int t = sc.nextInt(),k,l;
  13. while(t-- > 0){
  14. k = sc.nextInt();
  15. if(k==1){
  16. l = sc.nextInt();
  17. q.addElementToHeap(l);
  18. }
  19. else if(k==2){
  20. l = sc.nextInt();
  21. q.deleteArbitaryElement(l);
  22. }
  23. else if(k==3){
  24. System.out.println(root.data);
  25. }
  26. }
  27. System.out.println("Printing Heap:");
  28. // q.printMinHeap(root);
  29. long endTime = System.currentTimeMillis();
  30. System.out.println((double) (endTime - startTime) / 1000);
  31. sc.close();
  32. }
  33. private void addElementToHeap(int data){
  34. if(root==null){
  35. root = new MinimumHeap<>(data, null, null, null);
  36. h.put(data,count);
  37. count++;
  38. return;
  39. }
  40. if(count<1){
  41. System.out.println("underflow");
  42. return;
  43. }
  44. MinimumHeap<Integer> head = root;
  45. char[] path = getBinary(count).toCharArray();
  46. for(int i=path.length-2;i>=0;i--){
  47. if(path[i]=='0') {
  48. if(head.left == null) {
  49. if(data < head.data){
  50. int temp = data;
  51. data = head.data;
  52. head.data = temp;
  53. h.put(head.data, h.get(data));
  54. }
  55. head.left = new MinimumHeap<>(data, null, null, head);
  56. h.put(data, count);
  57. count++;
  58. return;
  59. }
  60. head = head.left;
  61. }
  62. else if(path[i]=='1') {
  63. if(head.right == null) {
  64. if(data < head.data){
  65. int temp = data;
  66. data = head.data;
  67. head.data = temp;
  68. h.put(head.data, h.get(data));
  69. }
  70. head.right = new MinimumHeap<>(data, null, null, head);
  71. h.put(data, count);
  72. count++;
  73. return;
  74. }
  75. head = head.right;
  76. }
  77. }
  78. }
  79.  
  80. private String getBinary(int data){
  81. StringBuilder res = new StringBuilder("");
  82. while(data>0){
  83. res.append(data%2);
  84. data = data/2;
  85. }
  86. return res.toString();
  87. }
  88.  
  89. private void deleteElementFromHeap(int data){
  90. while(root.data!=data){
  91. extractMin();
  92. }
  93. extractMin();
  94. }
  95. private void deleteArbitaryElement(int data){
  96. if(root==null) return;
  97. int aux=h.get(data);
  98. count--;
  99. if(count==1){
  100. root=null;
  101. return;
  102. }
  103. /*Tail takes us to the element to be deleted*/
  104. MinimumHeap<Integer> tail = root;
  105. // go to that element path
  106. char[] path = getBinary(aux).toCharArray();
  107. int i;
  108. // traverse the path and move along
  109. for(i=path.length-2;i>=0;i--) {
  110. if(path[i] == '0')
  111. tail = tail.left;
  112. else if(path[i] == '1')
  113. tail = tail.right;
  114. }
  115. // if the element to be deleted doesn't have any children i.e. it's a leaf
  116. // node, put it's parent left or right as null and return
  117. if(tail.left==null && tail.right==null){
  118. if(path[i+1]=='0')
  119. tail.parent.left=null;
  120. else if(path[i+1]=='1')
  121. tail.parent.right=null;
  122. return;
  123. }
  124. /*End takes us to the end of the tree*/
  125. MinimumHeap<Integer> end = root;
  126. path = getBinary(count).toCharArray();
  127. for(i=path.length-2;i>=0;i--) {
  128. if(path[i] == '0')
  129. end = end.left;
  130. else if(path[i] == '1')
  131. end = end.right;
  132. }
  133. // While removing last element, we check if it is attached to the left subtree
  134. // or right subtree and make the correspondent as null
  135. if(end.parent.left == end)
  136. end.parent.left=null;
  137. else if(end.parent.right == end)
  138. end.parent.right=null;
  139. tail.data = end.data;
  140. heapify(tail);
  141. }
  142.  
  143. private int extractMin(){
  144. if(root==null) return -1;
  145. // extract root element
  146. int min = root.data;
  147. // before heapifying reduce count to get total number of elements
  148. count--;
  149. // take tail at root
  150. if(count==1){
  151. root=null;
  152. return min;
  153. }
  154. MinimumHeap<Integer> tail = root;
  155. // get path to tail in order to replace that with root
  156. char[] path = getBinary(count).toCharArray();
  157. int i;
  158. // traverse the path and move along
  159. for(i=path.length-2;i>=0;i--) {
  160. if(path[i] == '0')
  161. tail = tail.left;
  162. else if(path[i] == '1')
  163. tail = tail.right;
  164. }
  165. // IMP: this is important, if we didn't link this, tail.parent.left will be
  166. // root(tail) and this ends up in infinite recursion, so make tail.parent.left
  167. // or right as null
  168. if(path[i+1] == '0')
  169. tail.parent.left = null;
  170. else if(path[i+1] == '1')
  171. tail.parent.right = null;
  172. // put tail.parent as null as tail will become new root
  173. tail.parent = null;
  174. // link root.left to tail.left and right, then point root to tail
  175. tail.left = root.left;
  176. tail.right = root.right;
  177. root = tail;
  178. // if there are more than 1 element that means root.left exists and link it's
  179. // parent to root similarly for right node
  180. if(count > 2)
  181. root.left.parent = root;
  182. if(count > 3)
  183. root.right.parent = root;
  184. // now heapify at root
  185. heapify(root);
  186. return min;
  187. }
  188.  
  189. private void heapify(MinimumHeap<Integer> head){
  190. // This condition never reaches, but just keeping it
  191. if(head==null)
  192. return;
  193. MinimumHeap<Integer> temp = head;
  194. if(head.left != null && head.left.data < temp.data){
  195. temp = head.left;
  196. }
  197. if(head.right != null && head.right.data < temp.data){
  198. temp = head.right;
  199. }
  200. if(temp != head){
  201. swap(head, temp);
  202. heapify(temp);
  203. }
  204. }
  205.  
  206. private void swap(MinimumHeap<Integer> node1, MinimumHeap<Integer> node2){
  207. //just swap their data not their entire sub-tree
  208. int temp = node1.data;
  209. node1.data = node2.data;
  210. node2.data = temp;
  211. h.put(node2.data, h.get(node1.data));
  212. h.put(node1.data, h.get(node2.data));
  213. /* if(node1.left == node2) {
  214. MinimumHeap temp = node1.right;
  215. MinimumHeap temp2 = node1.parent;
  216. node1.left = node2.left;
  217. node1.right = node2.right;
  218. node1.parent = node2;
  219. node2.left = node1;
  220. node2.right = temp;
  221. node2.parent = temp2;
  222. }
  223. else if(node1.right == node2){
  224. MinimumHeap temp = node1.left;
  225. MinimumHeap temp2 = node1.parent;
  226. node1.left = node2.left;
  227. node1.right = node2.right;
  228. node1.parent = node2;
  229. node2.right = node1;
  230. node2.left = temp;
  231. node2.parent = temp2;
  232. }*/
  233. }
  234.  
  235. private void printMinHeap(MinimumHeap root){
  236. if(root==null)
  237. return;
  238. /* TODO: iterative approach */
  239. System.out.println(root.data);
  240. printMinHeap(root.left);
  241. printMinHeap(root.right);
  242. }
  243. }
  244. class MinimumHeap<T>{
  245. protected T data;
  246. protected MinimumHeap<T> left;
  247. protected MinimumHeap<T> right;
  248. protected MinimumHeap<T> parent;
  249.  
  250. public MinimumHeap(T data, MinimumHeap<T> left, MinimumHeap<T> right, MinimumHeap<T>
  251. parent){
  252. this.data = data;
  253. this.left = left;
  254. this.right = right;
  255. this.parent = parent;
  256. }
  257.  
  258. }
Add Comment
Please, Sign In to add comment