[17일차] TIL - Heap

힙이란?

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)입니다.

 

최대힙과 최소힙은 완전이진트리에서 부모가 자식노드보다 큰 값을 가지거나(최대힙), 작은 값을 가지는(최소힙) 자료구조입니다.

 

힙 삽입(최대힙)

리프노드에 추가하고자하는 원소를 넣은 후 부모노드와 크기 비교를 합니다. 최대힙을 예로 들자면 추가한 노드가 부모노드보다 크다면 부모노드와 자리를 바꿉니다. 

 

완전이진트리의 최대높이는 O(log(N))입니다. 따라서 최악의 경우 맨 위 루트노드까지 올라갈 수 있으므로 

삽입시 시간 복잡도 역시 O(log(N)) 입니다.

 

• 삽입과정

1. 리프노드에 삽입하고자하는 원소를 추가합니다.

2. 부모노드와 비교하여 자신의 값보다 작다면 부모노드와 추가된 노드를 바꿉니다.

3. 2번 과정을 부모노드가 자신보다 크거나 같을 때까지 반복합니다.

 

힙 추출(최대힙)

완전이진트리의 중간에서 값을 빼는 방식은 힙에서는 존재하지 않습니다. 추출이라고 한다면 무조건 루트노드의 원소를 빼낸다고 생각하시면 되겠습니다.

 

추출시 시간 복잡도 역시 O(log(N)) 입니다.

 

• 추출 과정

1. 루트노드와 맨 끝 리프노드의 자리를 바꿉니다.

2. 리프노드로 간 기존 루트노드를 제거합니다.

3. 루트노드(기존 리프노드)를 좌우 노드 중 큰 값을 자신과 비교하여 자신보다 크다면 위치를 바꿉니다.

4. 3번 과정을 자식노드보다 자신이 클 때까지 반복합니다.

 

 

1. 배열의 k번째 큰 요소

https://leetcode.com/problems/kth-largest-element-in-an-array/submissions/

파이썬은 기본적으로 최소힙을 바탕으로 작동하기 때문에 최대힙을 구현하기 위해서는 코드를 조금 수정해 주어야합니다. 두가지 방법으로 풀이 해 보겠습니다.

 

튜플 형태로 heap에 저장시 튜플의 첫번째 원소를 기준으로 힙정렬을 하게됩니다. 따라서 음수값을 첫번째 원소로, 두번째 원소로는 값을 넣어서 최대힙으로 정렬하게끔 할 수 있습니다. 한가지 주의하셔야 할 점은 heappop으로 값을 return 할 때 [1]을 붙여서 튜플의 두번째 원소를 가져와야 한다는 점입니다.

def findKthLargest(self, nums: List[int], k: int) -> int:
        result = []
        for elem in nums:
            heapq.heappush(result, (-elem, elem))

        return [heapq.heappop(result) for _ in range(k)][k - 1][1]

 

heap에 원소를 넣을 때 처음부터 음수를 넣고 heappop으로 return 할 때 

마이너스를 붙여서 원래형태로 바꿔 가져와서 최대힙을 구현할 수 있습니다.

def findKthLargest(self, nums: List[int], k: int) -> int:
        result = []
        for elem in nums:
            heapq.heappush(result, -elem)

        return [-heapq.heappop(result) for _ in range(k)][k - 1]

 

아래 두 문제는 최소힙과 최대힙을 묻는 문제입니다. 위 문제를 푸셨다면 아래 두 문제는 문제만 잘 해석하면 코드 구현은 쉬울 것이라 생각합니다.

2. 최소 힙

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

 

내 풀이

import heapq
import sys

input = sys.stdin.readline
n = int(input())

cal = []
for _ in range(n):
    cal.append(int(input()))

result = []

for num in cal:
    if num == 0:
        if not result:
            print(0)
            continue
        print(heapq.heappop(result))
    else:
        heapq.heappush(result, num)

 

다음과 같이 코드를 조금 더 줄여볼 수 있습니다.

n = int(input())

result = []

for _ in range(n):
    num = int(input())
    if num == 0:
        if not result:
            print(0)
        else:
            print(heapq.heappop(result))
    else:
        heapq.heappush(result, num)

 

최소 힙을 조금 응용하면 풀 수 있는 문제였습니다.

3. 최대 힙

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

import heapq
import sys
input = sys.stdin.readline
n = int(input())

result = []
for _ in range(n):
    num = (int(input()))
    if num == 0:
        if not result:
            print(0)
            continue
        print(-heapq.heappop(result))
    else:
        heapq.heappush(result, -num)