자료구조 : 힙(heap)

 

우선순위 큐를 구현한 완전 이진 트리의 일종

 

우선순위 큐

 

스택 - 가장 최근에 입력된 데이터부터 추출

큐 - 가장 먼저 입력된 데이터부터 추출

우선순위 큐 - 가장 우선순위가 높은 데이터부터 추출

 

우선순위 큐를 힙, 배열, 연결리스트로 구현할 수 있는데, 그중 힙으로 구현한 것이 가장 효율적

 

우선순위 큐 구현	입력	추출
순서 없는 배열	O(1)	O(n)
순서 없는 연결리스트	O(1)	O(n)
순서대로 정렬된 배열	O(n)	O(1)
순서대로 정렬된 연결리스트	O(n)	O(1)
힙	O(log n)	O(log n)

 

 

특징과 종류

- 여러 값 가운데 최솟값이나 최댓값을 빠르게 찾을 수 있다

- 반정렬 상태(느슨한 정렬 상태)

- 중복값 허용

- 계산의 편리를 위해 첫번째 인덱스가 1부터 시작함

- 종류

     - 최대 힙 : key(부모 노드) >= key(자식 노드)

     - 최소 힙 : key(자식 노드) >= key(부모 노드)

 

 

구현

*인덱스가 1부터 시작한다면

부모노드 : $i$

왼쪽 자식 노드 : $2n$

오른쪽 자식 노드 : $2n+1$

-->  배열 형태로 트리를 저장한다

 

 

입력(삽입)

 

1. 힙의 마지막 노드 다음에 새로운 값을 삽입한다

2. 새로운 값과 부모 노드의 값을 비교해 자리를 찾을 때까지 교환한다

# 이진 힙 구현
class BinaryHeap(object): # 인덱스 0 비워둠
    def __init__(self):
        self.items = [None]
        
    def __len__(self): # 마지막 요소의 인덱스 가져오기 위함
        return len(self.items) - 1
        
# 삽입 -> heapq.heappush()
def _percolate_up(self):
    i = len(self) # index
    parent = i // 2 # 레벨 별 인덱스가 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() # 부모노드와 자리 바꾸기

 

추출(삭제)

1. 루트 노드를 삭제한다

2. 힙의 마지막 노드를 루트 자리에 둔다

3. 부모 노드와 자식 노드 관계를 비교해 교환한다

 

# 최소 힙 알고리즘 구현
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] # swap
        self._percolate_down(smallest)
        
# 추출 -> heapq.heappop()
def extract(self):
    extracted = self.items[1] # 루트 값 추출
    self.items[1] = self.items[len(self)]
    self.items.pop()
    self._percolate_down(1)
    return extracted