programmers-data-structure/MinHeap.py at main · seyeop03/programmers-data-structure · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
from collections import deque
# 골드1 최솟값 찾기
class MaxHeap:
    def __init__(self):
        self.data = [None]

    def insert(self, item):
        if len(self.data) == 1:
            self.data.append(item)
        else:
            cur = len(self.data)
            self.data.append(item)
            while cur != 0 and self.data[cur//2] > item:
                self.data[cur//2], self.data[cur] = self.data[cur], self.data[cur//2]
                cur //= 2
                if cur == 1:
                    break

    def maxHeapify(self, i):
        left = 2*i
        right = 2*i + 1
        smallest = i

        if len(self.data)-1 >= left and self.data[smallest] >= self.data[left]:
            smallest = left

        if len(self.data)-1 >= right and self.data[smallest] >= self.data[right]:
            smallest = right

        if smallest != i:
            self.data[smallest], self.data[i] = self.data[i], self.data[smallest]
            self.maxHeapify(smallest)

    def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)
        else:
            data = None
        return data


N, L = map(int, input().split())

l = list(map(int, input().split()))
heap = MaxHeap()
d = deque()
idx = 0
cnt = {}

mini = l[0]

while idx < L:
    if l[idx] in cnt:
        cnt[l[idx]] += 1 # count
    else:
        cnt[l[idx]] = 1
        heap.insert(l[idx])

    d.appendleft(l[idx])
    idx += 1
    if heap.data[1] >= mini:
        print(mini, end=' ')
    else:
        mini = heap.data[1]
        print(mini, end=' ')


for idx in range(L, N):
    d.appendleft(l[idx])
    if l[idx] in cnt:
        if cnt[l[idx]] == 0:
            heap.insert(l[idx])
        cnt[l[idx]] += 1
    else:
        cnt[l[idx]] = 1
        heap.insert(l[idx])

    prev = d.pop()
    cnt[prev] -= 1


    while cnt[heap.data[1]] == 0:
        heap.remove()

    mini = heap.data[1]

    print(mini, end=' ')