Cod sursa(job #1545792)

Utilizator cristinabCristina Brinza cristinab Data 7 decembrie 2015 03:44:43
Problema Heapuri Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 2.96 kb
//package heapuri;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.HashMap;

class Heap {
	private int[] heap;
	private int currentPosition;
	private int[] position;
	private HashMap<Integer, Integer> positionInHeap;
	private int counter;

	public Heap(int size) {
		currentPosition = 0;
		heap = new int[size + 1];
		position = new int[size + 1];
		positionInHeap = new HashMap<Integer, Integer>();
		counter = 0;
	}

	private void swap(int i, int j) {
		int aux = heap[i];
		heap[i] = heap[j];
		heap[j] = aux;
	}

	public void add(int x) {
		heap[++currentPosition] = x;
		position[++counter] = x;
		positionInHeap.put(x, currentPosition);
		
		int k = currentPosition;

		while (k > 1 && heap[k / 2] > heap[k]) {
			swap(k / 2, k);
			
			positionInHeap.put(heap[k / 2], k / 2);
			positionInHeap.put(heap[k], k);
			
			k = k / 2;
		}
	}
	
	public int min() {
		return heap[1];
	}

	private void heapify(int i) {
		int k = i;
		int leftChild = 2 * k;
		int rightChild = 2 * k + 1;
		int index = k;

		if (leftChild <= currentPosition && heap[k] > heap[leftChild]) {
			index = leftChild;
		}

		if (rightChild <= currentPosition && heap[rightChild] < heap[index]) {
			index = rightChild;
		}

		if (index != k) {
			swap(index, k);
			
			positionInHeap.put(heap[index], index);
			positionInHeap.put(heap[k], k);
			
			heapify(index);
		}
	}

	public int remove() {
		int removed = heap[1];
		heap[1] = heap[currentPosition--];
		
		positionInHeap.put(heap[1], 1);
		
		heapify(1);

		return removed;
	}

	public void print() {
		for (int i = 1; i <= currentPosition; i++) {
			System.out.print(heap[i] + " ");
		}
		System.out.println();
	}
	
	// delete element which was added position-th
	public void removeAdded(int position) {
		int valueToBeRemoved = this.position[position];
		int positionInHeap = this.positionInHeap.get(valueToBeRemoved);
		
		heap[positionInHeap] = heap[currentPosition--];
		this.positionInHeap.put(heap[positionInHeap], positionInHeap);
		
		heapify(positionInHeap);
	}
}

class Main {
	
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new FileReader("heapuri.in"));
			BufferedWriter bw = new BufferedWriter(new FileWriter("heapuri.out"));
				
			int n = Integer.parseInt(br.readLine());
			Heap heap = new Heap(n);
			
			for (int i = 0; i < n; i++) {
				String line = br.readLine();
				String[] split = line.split(" ");
				
				if (split[0].equals("1")) {
					heap.add(Integer.parseInt(split[1]));
				} else if (split[0].equals("2")) {
					int position = Integer.parseInt(split[1]);
					heap.removeAdded(position);
				} else if (split[0].equals("3")) {
					bw.write(heap.min() + "\n");
				}
			}
			
			br.close();
			bw.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}