Heap에 대해 알아보자

힙이란?

• 힙은 트리기반 자료구조이다.
• 파이썬에서 우선순위 큐를 사용할때 heapq 모듈을 통해 구현한다.(최소힙만 가능)
• 최소힙은 항상 부모가 자식보다 작다. 즉 추출은 항상 루트를 가져온다.
• 힙은 주로 배열로 구현 된다. 거의 완전한 트리(almost complete tree)이기에 부모나 자식의 접근을 인덱스로 효율적이게 가능하기 때문이다.
• 상하로만 관계있지, 좌우로는 관계 없다.

힙 vs 정렬

힙과 정렬의 차이로는 값의 삽입과 추출이 잦다면, 힙을 사용해 좀더 효율적으로 min or max를 유지할 수 있다. 반면 수정 삭제가 잦지 않다면 내장 라이브러리를 통한 sort를 사용하는게 더 직관적이고 용이하다.

---

힙의 활용 :

힙은 항상 균형을 유지하는 특성 때문에 다양한 분야에 널리 활용된다.

• 우선순위큐
• 다익스트라 알고리즘 (힙을 통해 O(V^2) 에서 O(ElogV)로 개선가능)
• 힙정렬
• 최소신장트리를 구현하는 Prim's Algoritm 등에도 활용
• 중앙값의 근사치를 빠르게 구하는데도 활용 (레벨의 중간노드를 추출하면 근사치로 가능)

---

Python을 통한 BinaryHeap 구현

class BinaryHeap(object) :
    
    def __init__(self) :
        self.items = [None]
    
    def __len__(self) :
        return len(self.items)-1
    
    # 삽입 시 실행, 반복 구조 구현
    def _percolate_up(self) : 
        i = len(self)
        parent = i // 2
        while parent > 0 :
            if self.items[i] < self.items[parent] :
                self.items[parent] , self.items[i] = \
                self.items[i] , self.items[parent]
            i = parent
            parent = i // 2
    def insert(self,k) :
        self.items.append(k)
        self._percolate_up()
            
    # 추출시 실행, 재귀 구조 구현
    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) :
        extracted = self.items[1]
        self.items[1] = self.items[len(self)]
        self.items.pop()
        self._percolate_down(1)
        return extracted
      

특징 :

index 1은 비워둔다. (계산의 용이성)

시간복잡도 :

• 추출,삽입시 힙을 유지하기 위해 log(n)의 시간 복잡도를 가진다.
• 추출 후 힙을 유지할 필요가 없다면 추출은 O(1)만에 가능하다.

---

이진힙 vs 이진탐색트리(BST)

이름이 비슷해 헷갈릴 수도 있지만 이 둘은 엄연히 다른 개념이다.
가장 직관적인 차이점은 힙은 상하관계를 보장하고, BST는 좌우관계를 보장한다.

---

파이썬의 Priority Queue 와 heapq의 차이

파이썬에서 우선 순위 큐는 heapq 뿐만 아니라, queue 모듈의 PriorityQueue를 통해 구현 할 수 도있다. 왜 같은기능을 하는 라이브러리가 2개나 있을까 궁금해서 찾아 보았다.
결론부터 말하자면, 파이썬의 PriorityQueue 조차 내부적으로 heapq를 사용하도록 구현되어있다.

Cpython에서 PriorityQueue의 내부를 보면, 아래와 같다.

class PriorityQueue(queue) :
	...
    def _put(self,item) :
    	heappush(self.queue,item)
    
    def _get(self) :
    	return heappop(self.queue)
        

그렇다면 둘의 차이점은 무엇일까?

차이점은 PriorityQueue는 스레드 세이프(멀티 스레드에서도 안전한 프로그래밍 개념 : 만약 스레드 세이프 하지 않다면, 1번 스레드에서 2번 스레드의 값을 바꿀 수 있다.) 하다는 점이다. heapq 모듈은 스레드 세이프를 보장하지 않는다.

그러나, 스레드 세이프 하다는 점은 Locking을 제공한다는 의미이고, 이는 오버헤드를 발생시킨다. 따라서 굳이 멀티 스레드로 구현할 게 아니라면 PriorityQueue를 사용하지 말자.

실무에서도 heapq로 우선순위 큐가 구현되고 있다고 한다.

참고자료 : '파이썬 알고리즘 인터뷰 - 박상길'