[자료구조] heap에 대해 알아보기

heap의 종류

• max heap: 트리 형태로 루트가 가장 큰 값이며, 부모 노드가 자식 노드보다 항상 큰 값
• min heap: 트리 형태로 루트가 가장 작은 값이며, 부모 노드가 자식 노드보다 항상 작은 값

max heap 예시
 
                     7
                   /   \
                 6       5
                / \     / \ 
               4   2   1   3    


min heap 예시

                     1
                   /   \
                 2       3
                / \     / \ 
               4   6   5   7    

heap의 시간 복잡도

• heap을 구성하는데에는 O(nlogn)
• root node(가장 큰 값 or 가장 작은 값)를 구할 때는 O(1)

max heap 정렬 구현 코드

heapify는 일반적인 트리를 heap으로 바꾸는 과정
siftdown에서 부모노드와 자식노드를 비교해서 자식노드가 부모노드보다 크다면 swap해줌

arr = [6,2,4,9,7,5,8]

                     6
                   /   \
                 2       4
                / \     / \ 
               9   7   5   8     
               
               
def heapsort(a):
    
    def heapify(a ,size):  # a는 배열, size는 총 갯수
        p = (size//2) - 1  # 자식 노드가 있는 맨 마지막의 부모 노드의 인덱스부터 확인(4의 위치, 인덱스:2)
        while p>=0:
            siftdown(a, p, size)
            p -= 1


    def swap(a,i,j):
        tmp = a[i]
        a[i] = a[j]
        a[j] = tmp


    # 부모노드의 양 자식노드를 비교하고 부모노드보다 더 큰 자식 노드가 있으면 swap
    def siftdown(a, i, size):
        l = 2*i+1  # 왼쪽 자식 노드 인덱스
        r = 2*i+2  # 오른쪽 자식 노드 인덱스
        largest = i
        if l <= size-1 and a[l] > a[i]:  # 왼쪽 자식노드가 인덱스 범위를 넘어가지 않으며, 부모노드 보다 크다면 swap
            largest = l
        if r <= size-1 and a[r] > a[largest]: # 오른쪽 자식노드가 인덱스 범위를 넘어가지 않으며, 부모노드 보다 크다면 swap
            largest = r
        if largest != i:
            swap(a, i, largest)
            siftdown(a, largest, size) # swap 이후 다시 자식 노드들에 대해서도 siftdown 진행
            
            
    size = len(a)
    heapify(a, size)
 
 -------------------------------------------
 
heapsort(arr)               
max_heap 정렬 후 -> [9, 7, 8, 2, 6, 5, 4]

                     9
                   /   \
                 7       8
                / \     / \ 
               2   6   5   4    

python에서 heapq 모듈 사용하기

python에는 최소 힙(min heap)을 사용할 수 있는 내장 모듈 heapq가 있다.

모듈 import 하기

import heapq

빈 리스트를 최소 힙으로 만들기

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)

------------
[1, 4, 3]

heappush()는 원소를 추가할 리스트와 추가할 원소를 인자로 받는다.

원소가 있는 리스트를 최소 힙으로 만들기

import heapq

heap = [3, 4, 1]
heapq.heapify(heap)

print(heap)

------------
[1, 4, 3]

heapify()는 리스트를 인자로 받아 최소 힙으로 만들어준다.

최소 힙에서 가장 작은 원소 꺼내기(삭제)

print(heapq.heappop(heap))
print(heap)
------------
1
[3, 4]

heappop()은 최소 힙에서 최소 값을 삭제하고 이를 반환해주며
다시 최소 힙 정렬을 수행한다.

최소 힙에서 가장 작은 원소 접근(삭제 X)

heap = [1, 4, 3]
print(heap[0])
------------
1

인덱스 [0] 으로 최상위 노드에 접근할 수 있다.

heapq에서 최대 힙 구현하기

import heapq

li = [3, 4, 1]
max_heap = []

for i in li:
    heapq.heappush(max_heap, ((-1)*i, i))
    
------------
[(-4, 4), (-3, 3), (-1, 1)]

리스트의 원소들에 -1을 곱하여 heap에 추가하게 되면 기존 리스트의 최댓값이 최소힙 최상단 노드에 위치하게 된다.

또한 heap은 첫번째 요소를 기준으로 정렬하기 때문에 튜플의 두번째 요소에 기존 값을 넣으면 이후 값을 꺼낼 때 인덱스 [1]로 기존 값에 접근할 수 있다.