[Python] 힙

1. 힙이란?

       1
     /   \
    3     4
   / \   /
  5   6 7

- 완전 이진 트리 Complete Binary Tree 형태를 갖는 자료구조이다.

-- 완전 : 마지막 레벨을 제외한 모든 레벨(깊이)에서 노드가 완전히 채워져 있다

-- 이진 : 모든 부모 노드는 2개의 자식 노드를 갖는다.

 

- 모든 부모 노드의 값은, 자식 노드보다 크거나 같다.

 

- 배열로 구현할 수 있다.

-- 인덱스 i 에 대해, 왼쪽 자식은 2i + 1 에, 오른쪽 자식은 2i + 2 에 위치한다.

-- 부모 노드는 (i - 1) // 2 에 위치한다.

1.1. 추가 과정(heapq.heappush)

1. 주어진 배열의 가장 마지막 인덱스에 값을 추가함

2. 추가한 값이 부모 노드보다 작다면, 부모 노드와의 위치를 바꿈

3. 과정 2.를 루트 노드까지 반복한다

1.2. 제거 과정(heapq.heappop)

1. 주어진 배열의 루트 인덱스를 제거함

2. 루트 인덱스에 현재 배열의 가장 마지막 인덱스에 있는 값을 옮김

3. 2개의 자식 노드 중, 더 작은 자식 노드와 값을 비교함. 더 작다면 위치를 바꿈

4. 과정 3.을 리프 노드까지 반복한다

 

2. 파이썬에서 이용하기

import heapq

# 최소 힙에서 value를 쓴다면
# 최대 힙은 value 대신 (-value, value) 형태로 배열의 원소를 구성하면 된다.

heapq.heappush(arr, value) # value 삽입
heapq.heappop(heap) # 가장 작은 원소 제거 후 반환
heapq.heapify(arr) # 리스트를 최소 힙으로 변환

- 파이썬에서의 힙은 최소 힙 이다. 즉, 모든 부모 노드는 자식 노드보다 값이 같거나 작다.

- 최대 힙 구현도 최소 힙의 성질을 이용하여 간단하게 구현할 수 있다.