Python

[좌충우돌, 파이썬으로 자료구조 구현하기] 힙(heap) 구현하기

Wix 2023. 9. 16. 15:02

큐(Queue)는 선입선출의 자료구조이다. 들어가는 자료에 우선순위를 매겨서 들어간 순서와 관계없이 나갈 때는 우선순위가 높은 자료가 먼저 나가는 구조를 우선순위 큐(Priority Queue)라고 한다.

 

힙(heap)이란, 우선순위 큐를 구현한 자료구조이다. 힙은 다음과 같은 규칙에 따라 구성한 이진트리이다.

 

규칙 1.  노드를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간다. (레벨 순서로 노드를 삽입한다.)

  • 위 그림은 모두 이진트리인데, (a)는 힙이지만 (b)는 힙이 아니다. 왜냐하면 (b)는 왼쪽에서 부터 채워져야한다는 규칙을 벗어났다.

규칙 2. 최소 힙은 부모 노드가 자식 노드의 값보다 작거나 같아야 한다. 파이썬의 heapq 모듈은 최소 힙(min heap)이다. (최대 힙은 부모 노드가 자식 노드의 값보다 크거나 같다.)

  • (a)는 힙이지만, (b)는 힙이 아니다. 왜냐하면 (b)의 부모노드 값이 5인 자식노드의 값이 4인 부분이 존재하기 때문이다.

파이썬의 heapq 모듈 구현하기

배열(리스트)을 이용하여 파이썬의 heapq 모듈을 구현하자.

 

왼쪽부터 꽉 채운 이진트리이므로, 배열을 이용해도 빈 곳이 생기지 않기 때문이다.

 

구현할 기능은 다음과 같다.

  • heappush(heap, data): heap에 data를 삽입
  • heappop(heap): heap에서 루트 노드의 값을 꺼낸 후 삭제
  • heapify(x): 배열 x를 힙 구조로 만든다.

heappush 구현하기

이미 힙 구조를 가진 배열의 끝에 새로운 원소를 추가하는 함수이다. 이 때, 추가된 원소가 부모보다 작으면 최소 힙 구조가 아니므로 부모와 자리를 바꾼다. 한번 자리를 바꿔 위로 올라간 요소의 부모 요소와도 비교하여 부모보다 작다면 계속 자리를 바꾼다.

  • 2를 가장 끝에 삽입한다.
  • 2가 부모 노드의 값인 6보다 작으므로 자리를 바꾼다.
  • 자리가 바뀐 2와 2의 부모 노드의 값인 3보다 값이 작으므로 다시 또 3과 자리를 바꾼다.
  • 힙을 조건을 만족했으므로, 끝낸다.

위를 코딩을 위해 단계별로 풀어서 정리해보면 다음과 같다.

 

1. 배열 끝에 새 값을 추가한다.

2. 추가한 원소의 인덱스 구한다.

3. 부모 인덱스를 구하여 서로의 값을 비교한다.

4. 새 값이 부모의 값보다 작으면 값을 교환한다.

  • 3번으로 돌아가서 같은 과정 반복하되, 루트에 도달 시 종료한다.

5. 새 값이 부모의 값보다 크거나 같으면 종료한다.

 

def heappush(heap,data):
    heap.append(data)
    currentIndex = len(heap) - 1
    
    while currentIndex > 0: # current(현재 원소의 인덱스)가 루트에 도달 시 종료
        parentIndex = (currentIndex - 1) // 2
        if heap[parentIndex] > heap[currentIndex]:
            heap[parentIndex], heap[currentIndex] = heap[currentIndex], heap[parentIndex]
            currentIndex = parentIndex
        else: # 새로 추가한 값과 부모 노드의 값 비교가 문제가 없으면 종료한다.
            break

실행 결과

import heapq
h1 = [3, 4, 6, 8, 5, 7]
h2 = [3, 4, 6, 8, 5, 7]

heappush(h1, 2)
heapq.heappush(h2, 2)

print("구현한 함수의 결과: ", h1)
구현한 함수의 결과:  [2, 4, 3, 8, 5, 7, 6]

print("heapq 메서드의 결과:", h2)
heapq 메서드의 결과: [2, 4, 3, 8, 5, 7, 6]

heappush(h1, 3)
heapq.heappush(h2, 3)

print("구현한 함수의 결과: ", h1)
구현한 함수의 결과:  [2, 3, 3, 4, 5, 7, 6, 8]

print("heapq 메서드의 결과:", h2)
heapq 메서드의 결과: [2, 3, 3, 4, 5, 7, 6, 8]

 

heappop 구현하기

heappop() 함수는 최소 힙에서 가장 작은 값을 추출하고 추출한 값을 반환하는 역할을 한다.

  • 루트 노드의 값 3을 임시 저장한다.
  • 마지막 노드인 7을 루트로 옮긴다.
  • 루트 노드 7을 자식 노드인 4와 6중 작은 값인 4와 자리를 바꾼다.
  • 다시 7을 자식 노드인 8과 5중 작은 값인 5와 자리를 바꾼다.

자식 노드 중 작은값과 자리를 바꾸는 이유는 만약 자식 노드 중 큰 값과 바꾸게 되면 다시 또 한번 자식 노드와 비교해야 하기 때문이다.

 

코드로 옮기기 전 풀이를 해본다.

 

1. heap이 비어있으면 "Empty Heap!"을 반환하고 종료

2. heap이 비어있지 않으면 힙의 길이를 확인하여 길이가 1인 경우, pop한 값을 반환한다.

3. 그렇지 않은 경우, 힙에서 가장 작은 값을 추출하기 위해 다음 과정을 실행한다.

  • 루트 노드의 값을 pop_data 변수에 저장한다. 왜냐하면, 최소 힙이기 때문에 루트 노드가 현재 최솟값이다.
  • 루트 노드에는 힙의 마지막 노드를 이동시키고 힙을 재정렬한다.

4. current 변수와 child 변수를 사용하여 힙을 재정렬한다.

  • current 변수는 현재 노드의 인덱스를 나타낸다.
  • child 변수는 현재 노드의 자식 노드 중 작은 값을 가진 자식 노드의 인덱스를 나타낸다.

5. 자식 노드의 인덱스가 heap의 길이보다 작으면 반복한다.

  • 현재 노드의 오른쪽 자식 노드의 인덱스를 구한다.
  • 자식 노드 중 더 작은 값의 index를 child 변수에 할당한다.
  • 현재 노드의 값이 자식 노드의 값보다 크면 자식 노드와 서로 교환한다.
    • current 변수의 index를 갱신하고, child 변수의 index를 현재 노드의 왼쪽 자식 노드의 인덱스로 할당한다.
  • 현재 노드의 값이 자식 노드보다 작으면 반복문을 벗어난다.
def heappop(heap):
    if not heap:
        return "Empty Heap!"
    elif len(heap) == 1:
        return heap.pop()
    
    pop_data, heap[0] = heap[0], heap.pop()
    current, child = 0, 1
    while child < len(heap):
        sibling = child + 1
        if sibling < len(heap) and heap[child] > heap[sibling]:
            child = sibling
        if heap[current] > heap[child]:
            heap[current], heap[child] = heap[child], heap[current]
            current = child
            child = current * 2 + 1
        else:
            break
    return pop_data

실행 결과

import heapq
h1 = [3, 4, 6, 8, 5, 7]
h2 = [3, 4, 6, 8, 5, 7]

data1 = heappop(h1)
data2 = heappop(h2)

print("구현한 함수 pop data =", data1)
>>> 구현한 함수 pop data = 3

print("구현한 함수 pop 이후: ", h1)
>>> 구현한 함수 pop 이후:  [4, 5, 6, 8, 7]

print("heapq 함수 pop data =", data2)
>>> heapq 함수 pop data = 3

print("heapq 함수 pop 이후: ", h2)
>>> heapq 함수 pop 이후:  [4, 5, 6, 8, 7]