Heap 구현 및 Python heapq

Heap 이란 거의 완전한 트리 기반의 자료구조이다.

거의 완전한 트리 기반으로 양쪽이 균형을 유지하는 특성을 가지기에 다음과 같은 알고리즘 및 자료구조를 구현하는데 사용된다.

• 우선순위 큐
• 다익스트라 알고리즘
• 힙 정렬
• 최소 신장 트리 ( MST )

Heap 자료구조를 python을 이용하여 직접 구현해보고, python에 내장된 heapq를 사용하는 방법에 대해 알아보자.

 

BinaryHeap 구현 ( Python )

class BinaryHeap():
    """
    Heap은 편의성을 위해 배열의 첫번째 인자를 None으로 놓고
    Index를 1부터 사용한다.
    """
    def __init__(self) -> None:
        self.items = [None]

    def __len__(self):
        return len(self.items) -1
    
    """
    INSERT 연산
    
    _percolate_up 함수를 이용하여 새롭게 추가된 원소를
    Root Parent까지 비교하여 SWAP 한다.
    Binary Tree의 높이만큼 Heapfy가 이루어지므로 연산의 복잡도는 logN 이다.
    """
    def _percolate_up(self):
        i = len(self)
        parent = i // 2
        while parent > 0:
            if self.items[i] < self.items[parent]:
                self.items[i], self.items[parent] = self.items[parent],self.items[i]
            i = parent
            parent = i // 2
    
    def insert(self,k):
        self.items.append(k)
        self._percolate_up()

    """
    EXTRACT 연산

    _percolate_down 연산을 이용하여 Root가 추출된 빈자리를 채울 원소를
    올바른 위치로 다시 heap을 구성한다.
    좌측 , 우측 현재를 비교하여 가장 작은 원소가 현재 원소가 될때까지 반복한다.
    
    Binary Tree의 높이만큼 Heapfy가 이루어지므로 연산의 복잡도는 logN 이다.
    """
    def _percolate_down(self,idx):
        left = idx * 2
        right = idx * 2 + 1
        smallest = idx

        if left <= len(self) and self.items[left] < self.items[smallest]:
            smallest = left

        if right <= len(self) and self.items[right] < self.items[smallest]:
            smallest = right

        if smallest != idx:
            self.items[idx],self.items[smallest] = self.items[smallest], self.items[idx]
            self._percolate_down(smallest)
    
    def extract(self) :
        if len(self) < 1:
            return None

        extracted = self.items[1]
        self.items[1] = self.items[len(self)]
        self.items.pop()
        self._percolate_down(1)
        return extracted


# BinaryHeap 인스턴스 생성 및 삽입
b_heap = BinaryHeap()
b_heap.insert(1)
b_heap.insert(5)
b_heap.insert(4)
b_heap.insert(2)
b_heap.insert(7)


# 모든 원소가 없어질때까지 추출
while len(b_heap) > 0:
    print(b_heap.extract())

"""
결과 ( 최소힙 구조로 작은 원소가 먼저 추출된다 )
1
2
4
5
7
"""

 

 

python에 내장된 heapq 모듈 사용

"""
주요 함수 목록
heapq.heapify(list) : 일반 배열을 최소 배열을 이용하 힙 구조로 재배치한다.
heapq.heappush(list,value) : 위에서 구조화한 힙 배열에 value 값을 힙 구조를 유지하며 추가한다.
heapq.heappush(list) : 위에서 구조화한 힙 배열의 root 값을(최소힙이므로 최소값) 힙 구조를 유지하며 추출한다.
"""

# 모듈 임포트
import heapq

arr = [1,5,4,2,7]

# heapify 함수를 이용하여 일반 배열인 arr을 Heap구조로 변경한다.
heapq.heapify(arr)

# arr 배열에 -1(원소)를 heap구조를 유지하며 추가한다. ( 즉 -1이 가장 작은 원소이므로 Root에 위치 )
heapq.heappush(arr,-1)

# heapr 구조를 유지하며 순서대로 원소를 추출한다.
while len(arr) > 0:
    print(heapq.heappop(arr))

"""
결과
-1
2
4
5
7
"""