[백준/python] 1927번, 11279번, 11286번: 최소, 최대, 절댓값 힙

문제

https://www.acmicpc.net/problem/1927

https://www.acmicpc.net/problem/11279

https://www.acmicpc.net/problem/11286

---

문제 요약

세 가지 힙은 다음과 같은 연산을 지원하는 자료구조이다.

 

1. 최소 힙

- 배열에 자연수 x를 넣는다.

- 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

 

2. 최대 힙

- 배열에 자연수 x를 넣는다.

- 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

 

3. 절댓값 힙

- 배열에 정수 x를 넣는다.

- 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

- 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

 

+ 프로그램은 처음에 비어있는 배열에서 시작한다.

 

N개의 연산을 진행한다. 

 

연산은 정수 x를 입력 받는다.

---

코드 (최소 힙)

import sys
input = sys.stdin.readline

from heapq import heappush, heappop

hq = []
# 우선 순위 큐로 사용할 배열

N = int(input())
# 연산 개수

for _ in range(N):
    num = int(input())
    if num == 0:
        if hq:
            print(heappop(hq)) # 우선 순위 큐에서 가장 우선 순위가 높은 요소 삭제 후 반환
        else:
            print(0)
    else:
        heappush(hq, num) # 우선 순위 큐 hp에 num 삽입
        # 파이썬에서 heappush는 default로 최소 힙을 갖는다.
        # 삽입과 동시에 정렬이 이루어진다.

---

코드 설명 (최소 힙)

최소 힙: 부모 노드의 키 값이 자식 노드보다 작거나 같은 완전 이진트리

+ 파이썬에서의 힙은 최소 힙이 default이다.

 

1. 우선 순위 큐(힙)로 사용할 빈 배열 hp를 만든다.

 

2. 연산 값 num을 차례대로 입력 받는다.

 

3. num이 0이 아니라면 우선 순위 큐 hp에 num을 삽입한다.

+ 삽입과 동시에 최소 힙으로 정렬이 이루어진다.

 

4. num이 0이라면 우선 순위 큐에서 가장 우선 순위가 높은 요소를 삭제하고 출력한다.

+ 큐가 비어 있다면, 0을 출력한다

---

코드 (최대 힙 )

import sys
input = sys.stdin.readline

from heapq import heappush, heappop

hq = []
# 우선 순위 큐로 사용할 배열

N = int(input())
# 연산 개수

for _ in range(N):
    num = int(input())
    if num == 0:
        if hq:
            print(-heappop(hq)) # 우선 순위 큐에서 가장 우선 순위가 높은 요소 삭제 후 반환
        else:
            print(0)
    else:
        heappush(hq, -num) # 우선 순위 큐 hp에 num 삽입
        # 파이썬에서 heappush는 default로 최소 힙을 갖는다.
        # 삽입과 동시에 정렬이 이루어진다.

---

코드 설명 (최대 힙)

최대 힙: 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전 이진트리

 

1. 우선 순위 큐(힙)로 사용할 빈 배열 hp를 만든다.

 

2. 연산 값 num을 차례대로 입력 받는다.

 

3. num이 0이 아니라면 우선 순위 큐 hp에 -num을 삽입한다.

+ 음수를 삽입하면, 최소 힙은 유지되지만, 절댓값을 기준으로 생각했을 때, 최대 힙이 된다.

+ 삽입과 동시에 최소 힙으로 정렬이 이루어진다.

 

4. num이 0이라면 우선 순위 큐에서 가장 우선 순위가 높은 요소를 삭제하고 다시 부호를 바꿔 출력한다.

+ 큐가 비어 있다면, 0을 출력한다.

---

코드 (절댓값 힙)

import sys
input = sys.stdin.readline

from heapq import heappush, heappop

hq = []
# 우선 순위 큐로 사용할 배열

N = int(input())
# 연산 개수

for _ in range(N):
    num = int(input())
    if num == 0:
        if hq:
            print(heappop(hq)[1]) # 우선 순위 큐에서 가장 우선 순위가 높은 요소 삭제 후 반환
        else:
            print(0)
    else:
        heappush(hq, (abs(num), num)) # 우선 순위 큐 hp에 num 삽입
        # 파이썬에서 heappush는 default로 최소 힙을 갖는다.
        # 삽입과 동시에 정렬이 이루어진다.

---

코드 설명 (절댓값 힙)

절댓값 힙: 부모 노드의 키 값의 절댓값이 자식 노드의 절댓값보다 작거나 같은 완전 이진트리

 

1. 우선 순위 큐(힙)로 사용할 빈 배열 hp를 만든다.

 

2. 연산 값 num을 차례대로 입력 받는다.

 

3. num이 0이 아니라면 우선 순위 큐 hp에 (num의 절댓값, num)을 삽입한다. (튜플 삽입)

+ 삽입한 값으로 배열이 들어오면, heappush는 0번 인덱스를 최우선 기준으로 힙 정렬한다.

+ 삽입과 동시에 최소 힙으로 정렬이 이루어진다.

 

4. num이 0이라면 우선 순위 큐에서 가장 우선 순위가 높은 요소를 삭제하고 1번 인덱스 값을 출력한다.

+ 큐가 비어 있다면, 0을 출력한다.

---

힙 구성 과정 (빈 트리부터 하나씩 추가)

1. 현재 들어올 노드를 우선 순위가 가장 낮다고 가정한 후, 트리의 맨 마지막 위치에 저장한다.

 

2 - 1. 부모 노드와 비교해 자신이 우선 순위가 더 높다면 부모 노드와 자리를 바꾼다.

 

2 - 2. 우선 순위가 낮다면 1번으로 돌아간다. (놔두고 다른 노드 추가)

 

3. 만약 트리의 루트라면 1번으로 돌아간다. (더 이상 비교할 부모 노드가 없다면)

 

+ 하나의 배열에 한 개에 힙만 있는 것이 아니라 조건만 충족되면 여러 개의 힙이 존재할 수 있다.