Created
March 10, 2021 20:59
-
-
Save solairerove/d1c50a0a88f72cab215e0955a27797dd to your computer and use it in GitHub Desktop.
Очереди с приоритетами stepik
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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