Untitled
raw download clone
TEXT
views 108
,
size 2578 b
/*************
 * Following is the main function for your reference which we are using internally.
 
 public static void main(String[] args) {
		PriorityQueue pq = new PriorityQueue();
		int choice = s.nextInt();
		while(choice != -1) {
			switch(choice) {
				case 1 : // insert
					int element = s.nextInt();
					pq.insert(element);
					break;
				case 2 : // getMax
					System.out.println(pq.getMax());
					break;
				case 3 : // removeMax
					System.out.println(pq.removeMax());
					break;
				case 4 : // size
					System.out.println(pq.getSize());
					break;
				case 5 : // isEmpty
					System.out.println(pq.isEmpty());
				default :
						return;
			}
			choice = s.nextInt();
		}
	}
************/
import java.util.*;
public class PriorityQueue {
	
	private ArrayList<Integer> heap;
	
	public int getSize() {
		return heap.size();
	}
	
	public boolean isEmpty() {
		return (heap.size() == 0);
	}
	
	public int getMax() {
		if(isEmpty()) {
			return Integer.MIN_VALUE;
		}
		return heap.get(0);
	}
	
	public void insert(int element) {
		heap.add(element);
		int childIndex = heap.size() - 1;
		int parentIndex = (childIndex - 1) / 2;
		
		while(true) {
			if(childIndex > 0 && heap.get(childIndex) > heap.get(parentIndex)) {
				int temp = heap.get(childIndex);
				heap.set(childIndex, heap.get(parentIndex));
				heap.set(parentIndex, temp);
				childIndex = parentIndex;
				parentIndex = (childIndex - 1) / 2;
			} else {
				return;
			}
		}
	}
	
	public int removeMax() {
		int max = getMax();
		heap.set(0, heap.get(getSize()-1));
		heap.remove(getSize()-1);
		
		int parentIndex = 0;
		int child1 = 1;
		int child2 = 2;
		
		while(true) {
			if (child1 >= heap.size() || child2 >= heap.size()) {
				if (child1 == heap.size() - 1 && heap.get(parentIndex) < heap.get(child1)) {
					int temp = heap.get(parentIndex);
					heap.set(parentIndex, heap.get(child1));
					heap.set(child1, temp);
				}
				break;
			} else if(heap.get(parentIndex) < Math.max(heap.get(child1), heap.get(child2))) {
				HashMap<Integer, Integer> map = new HashMap<>();
				map.put(heap.get(parentIndex), parentIndex);
				map.put(heap.get(child1), child1);
				map.put(heap.get(child2), child2);
				
				int m = Math.max(heap.get(child1), heap.get(child2));
				
				heap.set(parentIndex, m);
				heap.set(map.get(m), heap.get(parentIndex));
				
				parentIndex = map.get(m);
				child1 = 2*parentIndex + 1;
				child2 = 2*parentIndex + 2;
			}
		}
		return max;
	}
}
close fullscreen
Login or Register to edit or fork this paste. It's free.