Heap (힙)

개념

• 완전 이진 트리 (Complete Binary Tree) 형태의 자료구조
  • 완전 이진 트리란 ?
    • 루트(root) 노드부터 시작해 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree)
• 항상 루트 노드(root node)를 제거
• 그룹을 정렬(Heap Sort)하거나 데이터 안에서 최소/최대 값을 찾을 때 사용
• 삽입, 삭제 수행 시간 : O(logN)

종류

1️⃣ 최소 힙 (Min Heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작음
• 루트 노드가 가장 작은 값
• 값이 작은 데이터가 우선적으로 제거됨

2️⃣ 최대 힙 (Max Heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큼
• 루트 노드가 가장 큰 값
• 값이 큰 데이터가 우선적으로 제거됨

구현

• 일차원 배열로 구현
• 구현을 쉽게 하기 위해 배열의 1번째 인덱스인 0은 사용 X
• 특정 위치의 노드 번호는 새로운 노드 번호가 추가되어도 변하지 X
  • 루트 노드(1)의 오른쪽 노드는 항상 3

삽입 연산 - $O(logN)$

1. 트리의 가장 마지막 위치에 노드를 삽입
2. 추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인
3. 만족하지 않는다면 부모와 자식의 키 값을 교환
4. 조건에 만족하거나 추가된 노드가 루트에 도달할 때까지 2~3번 과정을 반복

삭제 연산 - $O(logN)$

1. 루트 노트를 삭제
2. 트리의 가장 마지막 노드를 루트 자리에 삽입
3. 바꾼 위치의 노드가 힙 조건을 만족하는지 확인
4. 만족하지 않는다면 왼쪽 자식과 오른쪽 자식 중 더 적합한(값이 더 큰) 노드와 교환
5. 조건을 만족하거나 리프 노드에 도달할 때까지 3~4번 과정을 반복

최소 힙 소스 코드 (Python)

• 힙은 우선순위가 높은 자료구조부터 빼기 때문에 힙에 넣었다 빼면 자동으로 오름차순 정렬이 됨

import heapq

# 오름차순 힙 정렬 (Heap Sort)
def heapsort(iterable):
	h = []
    res = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
    	heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
    	res.append(heapq.heappop(h))
    return res

최대 힙 소스 코드 (Python)

• Python에서는 기본적으로 최소 힙을 제공하므로 데이터의 부호를 바꿔서 넣은 후에 데이터의 부호를 바꿔서 빼서 최대 힙 사용 가능

import heapq

# 내림차순 힙 정렬 (Heap Sort)
def heapsort(iterable):
	h = []
    res = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
    	heapq.heappush(h, -value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
    	res.append(-heapq.heappop(h))
    return res

활용

우선순위 큐 (Priority Queue)

개념

• 각 데이터에 우선 순위를 부여해 큐에 넣은 데이터를 꺼낼 때, 우선 순위가 가장 높은 데이터를 가장 먼저 꺼내는 자료구조

특징

• 주로 정의된 우선 순위를 Heap Condition으로 갖는 힙(Heap)으로 구현
  • 리스트를 이용해서도 구현 가능
• 연산
  • 큐에 데이터를 우선순위를 지정해 추가
  • 큐에서 가장 우선 순위가 높은 데이터를 제거하고 반환

시간 복잡도

• 리스트로 구현하는 경우
  • 삽입 시간 : $O(1)$
  • 삭제 시간 : $O(N)$
• 힙으로 구현하는 경우
  • 삽입 시간 : $O(logN)$
  • 삭제 시간 : $O(logN)$
• 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업 (= 힙 정렬)
  • $O(NlogN)$