Skip to content

Instantly share code, notes, and snippets.

@solairerove
Created March 10, 2021 20:59
Show Gist options
  • Save solairerove/d1c50a0a88f72cab215e0955a27797dd to your computer and use it in GitHub Desktop.
Save solairerove/d1c50a0a88f72cab215e0955a27797dd to your computer and use it in GitHub Desktop.
Очереди с приоритетами stepik
import java.util.Scanner;
import java.util.Arrays;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
MaxPQ pq = new MaxPQ();
int cnt = 0;
while (cnt < n) {
String operation = sc.nextLine();
if (operation == null || operation.isEmpty()) {
continue;
}
cnt++;
//System.out.println(operation);
String[] split = operation.split(" ");
//System.out.println(Arrays.toString(split));
if (split.length == 2) {
pq.insert(Integer.valueOf(split[1]));
} else {
System.out.println(pq.delMax());
}
}
}
}
class MaxPQ {
private Integer[] pq;
private Integer n;
public MaxPQ(int capacity) {
pq = new Integer[capacity + 1];
n = 0;
}
public MaxPQ() {
this(1);
}
public boolean isEmpty() {
return n == 0;
}
public Integer size() {
return n;
}
public Integer max() {
return pq[1];
}
public void insert(int x) {
if (n == pq.length - 1) resize(pq.length * 2);
pq[++n] = x;
swim(n);
}
public Integer delMax() {
Integer max = pq[1];
swap(1, n--);
sink(1);
pq[n + 1] = null;
if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2);
return max;
}
private void resize(int capacity) {
Integer[] temp = new Integer[capacity];
if (n >= 0) System.arraycopy(pq, 1, temp, 1, n);
pq = temp;
}
private void swim(int k) {
while (k > 1 && less(k / 2, k)) {
swap(k / 2, k);
k = k / 2;
}
}
private void sink(int k) {
while (2 * k <= n) {
int j = k * 2;
if (j < n && less(j, j+1)) j++;
if (!less(k, j)) break;
swap(k, j);
k = j;
}
}
private boolean less(int i, int j) {
return pq[i] < pq[j];
}
private void swap(int i, int j) {
int temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment