Data structures (with python) - 3. Heap

Data structures (with python) - 3. Heap

 

💡 Heap is a tree-based data structure that follows the properties of a complete binary tree and is either a Min Heap or a Max Heap.

힙은 완전한 이진 트리의 속성을 따르는 트리 기반 데이터 구조로, 최소 힙 또는 최대 힙 중 하나입니다.

 

힙(Heap)은 이진트리의 일종으로, 특정한 규칙을 가지고 있는 자료 구조이다.

(Tree 는 이진트리, 밸런스 트리, 언밸런스 트리 등등을 차후 다룬다.)

 

힙은 두가지 종류가 있습니다.

 

최대 힙(Max heap) , 최소 힙(Min Heap)

 

최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같다.

= 즉, 루트 노드가 가장 큰 값을 가진다.

 

최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 가탇.

= 즉, 루트 노드가 가장 작은 값을 가진다.

 

힙은 우선순위 큐(Queue)를 구현하는데 주로 사용되며, 이외에도 힙 정렬, 그래프 알고리즘 등 다양한 곳에 활용된다.

(큐(Queue) 는 FIFO(First In, First Out) 구조를 가진 자료구조이다. 줄을 서는 것과 유사하며 차후 다룬다.)

 

 

파이썬에서 힙(Heap)을 구현해보려면 heapq 모듈로 쉽게 구현할 수 있다.

import heapq

heap = []

 heapq 모델은 기본적으로 최소 힙을 제공한다.

 

이제 힙에 원소를 조작해보자.

 

# 힙에 원소 추가
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
print(heap)  # 출력: [1, 4, 7]

# 힙에 원소 삭제
print(heapq.heappop(heap))  # 가장 작은 원소 삭제 후 출력: 1
print(heap)  # 출력: [4, 7]


# 기존 리스트를 힙으로 변환
nums = [4, 1, 7, 3, 8, 5]
heapq.heapify(nums)
print(nums)  # 출력: [1, 3, 5, 4, 8, 7]

 

주의점은 heapq 모듈은 최소 힙만을 지원하므로,

최대 힙을 구현하려면 원소의 부호를 바꿔서 넣고 꺼낼 때 다시 바꿔주는 방법을 사용해야 한다.

 

언제 최대 힙을 사용할까?

원소들 중에서 가장 큰 원소를 빠르게(!) 찾아야 할 경우이다.

이런 경우에는 최대 힙(Max heapq)을 구현해야 하는데, heapq 모듈은 최대 힙을 지원하지 않는다.

 

이런 상황에서 사용할 수 있는 간단한 방법은

원소에 힙을 추가할 때 그 값의 부호를 바꾸어 넣는 것이다.

즉, 양수를 음수로, 음수를 양수로 바꾸어 넣는다.

 

그러면 원래 가장 큰 원소가 가장 작은 것으로 간주, 힙의 루트 노드에 오게 된다.

원소를 꺼낼 떄는 다시 붛를 바꿔 원래의 값을 얻는다.

 

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

# 원소를 힙에 추가할 때 부호를 바꿔서 넣음
for num in nums:
    heapq.heappush(heap, -num)

# 원소를 꺼낼 때 부호를 다시 바꿔 원래의 값을 얻음
print(-heapq.heappop(heap))  # 출력: 8
print(-heapq.heappop(heap))  # 출력: 7

 

 

 

Heap 과 관련된 알고리즘

 

1. 힙 정렬(Heap sort)

 최대 힙을 구성한 후, 힙의 루트 노드(최대값)를 배열 마지막 요소와 교환, 힙의 크기를 1 줄인다.

 이 과정을 반복하면 배열이 오름차 순으로 정렬된다.

 

2. 우선순위 큐(Priority Queue)

  우선 순위 큐는 각 원소가 우선순위를 가지고 있고, 우선순위가 가장 높은 원소부터 꺼내 사용하는 자료구조이다.

  힙은 우선순위 큐를 구현하는데 많이 사용된다.

 

3. 다익스트라 알고리즘(Dijkstra's Algorithm)

  앞서 2-4. Graph representation 의 2-4-2. adjacency list에서 언급만 하고 넘어갔는데,

(https://parkpakrsu.tistory.com/330)

다익스트라 알고리즘은 그래프의 한 노드에서 다른 노드로 가는 최단 경로를 찾는 알고리즘이다.

이 알고리즘은 우선순위 큐를 사용해 구현되며, 이 때 힙이 주로 사용된다.

 

4. 히프화(Heapify)

  히프화는 주어진 데이터를 힙 구조를 만족하도록 재배열 하는 과정.

  주로 힙 정렬, 힙 생성 등에 사용된다.