11279_최대힙

문제는 더보기!

 

최대 힙

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음) (하단 참고)

256 MB

39629

17521

13561

45.594%

문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1 복사

13
0
1
2
0
0
3
2
1
0
0
0
0
0

예제 출력 1 복사

0
2
1
3
2
1
0
0

 

 

 

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap

[자료구조] 그림으로 알아보는 힙(Heap)

 

먼저 위의 힙 자료구조에 대한 이해를 보고 오는것이 좋을 것 같다. 

 

위 자료구조를 이해하였다면 그대로 만들기만 하면 된다!!

 

 

import sys

n = int(sys.stdin.readline())
heap = [ 0 ]
idx = 0




for _ in range(n):
    i = int(sys.stdin.readline())
    if i == 0 :
        if idx ==0:
            print(0)
        elif idx ==1:
            print(heap.pop())
            idx-=1
        else:
            print(heap[1])
            heap[1] = heap.pop()
            idx -=1

            tmp_idx = 1
            while tmp_idx*2 <= idx:

                if heap[tmp_idx] < heap[tmp_idx * 2]:
                    heap[tmp_idx], heap[tmp_idx * 2] = heap[tmp_idx * 2], heap[tmp_idx]

                if tmp_idx*2+1 <= idx and heap[tmp_idx] < heap[tmp_idx*2 + 1]:
                    heap[tmp_idx], heap[tmp_idx * 2+1] = heap[tmp_idx * 2+1], heap[tmp_idx]
                tmp_idx *=2

    else:
        heap.append(i)
        idx += 1

        tmp_idx = idx
        while (heap[tmp_idx] > heap[tmp_idx // 2]) and (tmp_idx > 1):
            heap[tmp_idx], heap[tmp_idx // 2] = heap[tmp_idx // 2], heap[tmp_idx]
            tmp_idx = tmp_idx//2

    print(heap)

 

 

파이썬의 heapq모듈을 이용하면 보다 쉽게 이용할 수 있다

 

 

import heapq
import sys

n = int(sys.stdin.readline())
heap = []

for _ in range(n):
    num = int(sys.stdin.readline())

    if num ==0:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)
    else:
        heapq.heappush(heap,[-num,num])