白駿1655)真ん中を言う

アルゴリズムの授業で、バイナリツリーのpeekを中間値にするためにminheapとmaxheapの2つの部分を実現したのを覚えています.
ではminheapとmaxheapにinput値を追加し、完全バイナリツリーを作成すればいいです.

左がminheap、右がmaxheapで、入力値はminheapから入力されます.入力した値がminHeapより小さい場合は、maxHeapを入力します.

どこにどんな値を追加しますか?考えてみれば、minHeapのpeekより小さい場合は、peekの位置を占めるためにmaxHeapにいくつかのぼかし値(中間値所定値)を追加する必要があります.

本当の小数と大数はpeekの位置を占めることができなくて、

でも「minheap maxheap maxheap maxheap mall bang」をすると、一番高い価格が横から出てくるので、

を並べ替えて完全なバイナリツリーを維持
並べ替える必要があるようです.そうしないとpeekの位置は変わりません.
一方,AVLツリーを実現した際にBF値が2であれば並べ替えたことを思い出した.
PriorityQueueはポーリングをポーリングに変えているので、交代ではなく片手を出して置いています.

の両側の最大値を出力し、minheapが1つ多い場合はminheap peek値を出力します.

「minheapページが1つ増えた~」サイズが奇数の場合は、中間値出力を追加します.
maxHeapはminHeapを構成する値より小さい値を集約するために設計された状態であり、この条件がなければ2つのうちの最高値のみが出力され、寸法が奇数の場合、maxHeapのpeekはすべての最高値条件を持ち去る.
e.g.{3,4,5}/{2,1}は3を出力するが,2を出力する.
したがって、これらの条件を考慮すると、コードの作成は以下のようになります.

public class M1655가운데를말해요 {
    private final static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private final static StringBuffer sb = new StringBuffer();
    private static PriorityQueue<Integer> minHeap, maxHeap;

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int input;

        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < N; i++) {
            input = Integer.parseInt(br.readLine());

            if (!minHeap.isEmpty() && minHeap.peek() > input) {
                maxHeap.add(input);
            } else {
                minHeap.add(input);
            }

            int BF = Math.abs(maxHeap.size() - minHeap.size());
            if(BF == 2) {
                rotate();
            }

            if (minHeap.isEmpty()) {
                sb.append(maxHeap.peek()).append("\n");
            } else if (maxHeap.isEmpty() || minHeap.size() - maxHeap.size() == 1) {
                sb.append(minHeap.peek()).append("\n");
            } else {
                sb.append(Math.min(maxHeap.peek(), minHeap.peek())).append("\n");
            }

        }
        System.out.println(sb);
    }

    private static void rotate() {
        if (maxHeap.size() > minHeap.size()) {
            minHeap.add(maxHeap.poll());
        } else {
            maxHeap.add(minHeap.poll());
        }
    }

まとめると、maxheapには小値があり、minheapには大値の2つのお尻と2つのお尻のパンの間の最も上昇を加えて完全な異叉樹を構成している.

+

優先キューとHeapの関係は、優先キューがインタフェース、抽象形式であり、Heapが実装形式であると理解される.