Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.HashMap;
- import java.util.Scanner;
- public class QHEAP1 {
- private static int count = 1;
- private static MinimumHeap<Integer> root = null;
- HashMap<Integer,Integer> h = new HashMap<>();
- public static void main(String args[]) {
- long startTime = System.currentTimeMillis();
- Scanner sc = new Scanner(System.in);
- QHEAP1 q = new QHEAP1();
- int t = sc.nextInt(),k,l;
- while(t-- > 0){
- k = sc.nextInt();
- if(k==1){
- l = sc.nextInt();
- q.addElementToHeap(l);
- }
- else if(k==2){
- l = sc.nextInt();
- q.deleteArbitaryElement(l);
- }
- else if(k==3){
- System.out.println(root.data);
- }
- }
- System.out.println("Printing Heap:");
- // q.printMinHeap(root);
- long endTime = System.currentTimeMillis();
- System.out.println((double) (endTime - startTime) / 1000);
- sc.close();
- }
- private void addElementToHeap(int data){
- if(root==null){
- root = new MinimumHeap<>(data, null, null, null);
- h.put(data,count);
- count++;
- return;
- }
- if(count<1){
- System.out.println("underflow");
- return;
- }
- MinimumHeap<Integer> head = root;
- char[] path = getBinary(count).toCharArray();
- for(int i=path.length-2;i>=0;i--){
- if(path[i]=='0') {
- if(head.left == null) {
- if(data < head.data){
- int temp = data;
- data = head.data;
- head.data = temp;
- h.put(head.data, h.get(data));
- }
- head.left = new MinimumHeap<>(data, null, null, head);
- h.put(data, count);
- count++;
- return;
- }
- head = head.left;
- }
- else if(path[i]=='1') {
- if(head.right == null) {
- if(data < head.data){
- int temp = data;
- data = head.data;
- head.data = temp;
- h.put(head.data, h.get(data));
- }
- head.right = new MinimumHeap<>(data, null, null, head);
- h.put(data, count);
- count++;
- return;
- }
- head = head.right;
- }
- }
- }
- private String getBinary(int data){
- StringBuilder res = new StringBuilder("");
- while(data>0){
- res.append(data%2);
- data = data/2;
- }
- return res.toString();
- }
- private void deleteElementFromHeap(int data){
- while(root.data!=data){
- extractMin();
- }
- extractMin();
- }
- private void deleteArbitaryElement(int data){
- if(root==null) return;
- int aux=h.get(data);
- count--;
- if(count==1){
- root=null;
- return;
- }
- /*Tail takes us to the element to be deleted*/
- MinimumHeap<Integer> tail = root;
- // go to that element path
- char[] path = getBinary(aux).toCharArray();
- int i;
- // traverse the path and move along
- for(i=path.length-2;i>=0;i--) {
- if(path[i] == '0')
- tail = tail.left;
- else if(path[i] == '1')
- tail = tail.right;
- }
- // if the element to be deleted doesn't have any children i.e. it's a leaf
- // node, put it's parent left or right as null and return
- if(tail.left==null && tail.right==null){
- if(path[i+1]=='0')
- tail.parent.left=null;
- else if(path[i+1]=='1')
- tail.parent.right=null;
- return;
- }
- /*End takes us to the end of the tree*/
- MinimumHeap<Integer> end = root;
- path = getBinary(count).toCharArray();
- for(i=path.length-2;i>=0;i--) {
- if(path[i] == '0')
- end = end.left;
- else if(path[i] == '1')
- end = end.right;
- }
- // While removing last element, we check if it is attached to the left subtree
- // or right subtree and make the correspondent as null
- if(end.parent.left == end)
- end.parent.left=null;
- else if(end.parent.right == end)
- end.parent.right=null;
- tail.data = end.data;
- heapify(tail);
- }
- private int extractMin(){
- if(root==null) return -1;
- // extract root element
- int min = root.data;
- // before heapifying reduce count to get total number of elements
- count--;
- // take tail at root
- if(count==1){
- root=null;
- return min;
- }
- MinimumHeap<Integer> tail = root;
- // get path to tail in order to replace that with root
- char[] path = getBinary(count).toCharArray();
- int i;
- // traverse the path and move along
- for(i=path.length-2;i>=0;i--) {
- if(path[i] == '0')
- tail = tail.left;
- else if(path[i] == '1')
- tail = tail.right;
- }
- // IMP: this is important, if we didn't link this, tail.parent.left will be
- // root(tail) and this ends up in infinite recursion, so make tail.parent.left
- // or right as null
- if(path[i+1] == '0')
- tail.parent.left = null;
- else if(path[i+1] == '1')
- tail.parent.right = null;
- // put tail.parent as null as tail will become new root
- tail.parent = null;
- // link root.left to tail.left and right, then point root to tail
- tail.left = root.left;
- tail.right = root.right;
- root = tail;
- // if there are more than 1 element that means root.left exists and link it's
- // parent to root similarly for right node
- if(count > 2)
- root.left.parent = root;
- if(count > 3)
- root.right.parent = root;
- // now heapify at root
- heapify(root);
- return min;
- }
- private void heapify(MinimumHeap<Integer> head){
- // This condition never reaches, but just keeping it
- if(head==null)
- return;
- MinimumHeap<Integer> temp = head;
- if(head.left != null && head.left.data < temp.data){
- temp = head.left;
- }
- if(head.right != null && head.right.data < temp.data){
- temp = head.right;
- }
- if(temp != head){
- swap(head, temp);
- heapify(temp);
- }
- }
- private void swap(MinimumHeap<Integer> node1, MinimumHeap<Integer> node2){
- //just swap their data not their entire sub-tree
- int temp = node1.data;
- node1.data = node2.data;
- node2.data = temp;
- h.put(node2.data, h.get(node1.data));
- h.put(node1.data, h.get(node2.data));
- /* if(node1.left == node2) {
- MinimumHeap temp = node1.right;
- MinimumHeap temp2 = node1.parent;
- node1.left = node2.left;
- node1.right = node2.right;
- node1.parent = node2;
- node2.left = node1;
- node2.right = temp;
- node2.parent = temp2;
- }
- else if(node1.right == node2){
- MinimumHeap temp = node1.left;
- MinimumHeap temp2 = node1.parent;
- node1.left = node2.left;
- node1.right = node2.right;
- node1.parent = node2;
- node2.right = node1;
- node2.left = temp;
- node2.parent = temp2;
- }*/
- }
- private void printMinHeap(MinimumHeap root){
- if(root==null)
- return;
- /* TODO: iterative approach */
- System.out.println(root.data);
- printMinHeap(root.left);
- printMinHeap(root.right);
- }
- }
- class MinimumHeap<T>{
- protected T data;
- protected MinimumHeap<T> left;
- protected MinimumHeap<T> right;
- protected MinimumHeap<T> parent;
- public MinimumHeap(T data, MinimumHeap<T> left, MinimumHeap<T> right, MinimumHeap<T>
- parent){
- this.data = data;
- this.left = left;
- this.right = right;
- this.parent = parent;
- }
- }
Add Comment
Please, Sign In to add comment