[Python] 1927번 최소 힙 / 11279번 최대 힙 / 11286번 절댓값 힙

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

1927번: 최소 힙

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

11279번: 최대 힙

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

11286번: 절댓값 힙

---

 

22/09/13

 

 

이 날에는 작정하고 클래스 3+에 있는 문제를 해결하고자 했다.

 

일명 힙 3대장.

 

최소 힙, 최대 힙에 관한 내용은 아래 링크를 참고했다.

https://velog.io/@jaenny/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99-%EC%B5%9C%EC%86%8C%ED%9E%99-%EC%B5%9C%EB%8C%80%ED%9E%99

[자료구조 힙] 최소힙, 최대힙

 

이 내용을 보고 최소 힙과 최대 힙을 그대로 구현했다. 자세한 내용은 위의 링크를 참고하면 될 것이다.

---

 

문제 접근 방식:

 

 

위에서 말한 것처럼 import heapq를 하지 않고 직접 구현하여 풀었다.

 

왠지 그래야 공부가 될 것 같아서 그렇게 구현하였다.

 

최대 힙은 최소 힙에서 부등호 방향만 반대로 바꾸면 끝이니 매우 쉽다.

 

절댓값 힙은 최소 힙의 변형이었다. 기본적으로 add함수는 최소 힙에 abs를 붙이면서 구현해주는데, 절댓값이 같은 경우 더 작은 값을 출력한다고 했으므로, 절댓값이 같은 경우는 더 작은 값이 부모 노드로 가도록 구현한다.

 

마찬가지로 pop 하는 함수를 구현할 때도 기본적으로 최소 힙+abs인데, 절댓값이 같은 케이스만 하나 더 추가해줘서 구현해주었다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1927번 최소 힙
# 자료 구조, 우선순위 큐
import sys
input = sys.stdin.readline

N = int(input())
min_heap = [0]

def min_heap_add(num):
    min_heap.append(num)
    now_index = len(min_heap) - 1
    while now_index != 1 and num < min_heap[now_index//2]:
        min_heap[now_index], min_heap[now_index//2] = min_heap[now_index//2], min_heap[now_index]
        now_index = now_index//2

def min_heap_pop():
    if len(min_heap) == 1:
        return 0
    min_heap[-1], min_heap[1] = min_heap[1], min_heap[-1]
    min_ele = min_heap.pop()
    p_index = 1
    while True:
        c_index = p_index * 2
        if (c_index + 1 < len(min_heap) and min_heap[c_index] > min_heap[c_index + 1]):
            c_index += 1
        if (c_index >= len(min_heap) or min_heap[c_index] > min_heap[p_index]):
            break
        min_heap[c_index], min_heap[p_index] = min_heap[p_index], min_heap[c_index]
        p_index = c_index
    return min_ele

for _ in range(N):
    num = int(input())
    if num == 0:
        print(min_heap_pop())
    else:
        min_heap_add(num)

# 11279번 최대 힙
# 자료 구조, 우선순위 큐
import sys
input = sys.stdin.readline

N = int(input())
max_heap = [0]

def max_heap_add(num):
    max_heap.append(num)
    now_index = len(max_heap) - 1
    while now_index != 1 and num > max_heap[now_index//2]:  # 부모 노드가 더 작을 동안
        max_heap[now_index], max_heap[now_index//2] = max_heap[now_index//2], max_heap[now_index]
        now_index = now_index//2

def max_heap_pop():
    if len(max_heap) == 1:
        return 0
    max_heap[-1], max_heap[1] = max_heap[1], max_heap[-1]
    max_ele = max_heap.pop()
    p_index = 1
    while True:
        c_index = p_index * 2
        if (c_index + 1 < len(max_heap) and max_heap[c_index] < max_heap[c_index + 1]):
            c_index += 1
        if (c_index >= len(max_heap) or max_heap[c_index] < max_heap[p_index]):
            break
        max_heap[c_index], max_heap[p_index] = max_heap[p_index], max_heap[c_index]
        p_index = c_index
    return max_ele

for _ in range(N):
    num = int(input())
    if num == 0:
        print(max_heap_pop())
    else:
        max_heap_add(num)

# 11286번 절댓값 힙
# 자료 구조, 우선순위 큐
import sys
input = sys.stdin.readline

N = int(input())
heap = [0]

def heap_add(num):
    heap.append(num)
    now_index = len(heap) - 1
    while True:
        if now_index == 1 or abs(num) > abs(heap[now_index//2]):
            break
        if abs(num) == abs(heap[now_index//2]) and num > heap[now_index//2]:
            break
        heap[now_index], heap[now_index//2] = heap[now_index//2], heap[now_index]
        now_index = now_index//2

def heap_pop():
    if len(heap) == 1:
        return 0
    heap[-1], heap[1] = heap[1], heap[-1]
    ele = heap.pop()
    p_index = 1
    while True:
        c_index = p_index * 2
        if (c_index + 1 < len(heap) and abs(heap[c_index]) > abs(heap[c_index + 1])):
            c_index += 1
        elif (c_index + 1 < len(heap) and abs(heap[c_index]) == abs(heap[c_index + 1]) and heap[c_index] > heap[c_index + 1]):
            c_index += 1
        if c_index >= len(heap) or abs(heap[c_index]) > abs(heap[p_index]):
            break
        elif abs(heap[c_index]) == abs(heap[p_index]) and heap[c_index] > heap[p_index]:
            break
        heap[c_index], heap[p_index] = heap[p_index], heap[c_index]
        p_index = c_index
    return ele

for _ in range(N):
    num = int(input())
    if num == 0:
        print(heap_pop())
    else:
        heap_add(num)