자료구조 - 우선순위 큐 (부제: 우선순위 큐와 힙은 어떤 관계일까?)

 

 

<우선순위 큐>

<힙>

#우선순위 큐를 구현하기 위해서 사용하는 자료구조 = 힙

 

#힙 = 내부적으로 트리구조를 사용하기 때문에 삽입과 삭제에 있어서 O(logN) 시간만큼 걸린다.

 

<힙 라이브러리 사용 예제 코드: 최소 힙>

import heapq

#오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    
    #모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h,value)
        #힙푸시의 경우 특정 리스트에 어떤 데이터를 넣을 수 있다.
        #넣는 경우엔 그냥 들어온 순서대로 넣고 나올 때 가장 우선순위가 낮은 것부터 빼낸
        
        
    #힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
        #힙팝의 경우엔 리스트에서 데이터를 꺼낼 때 사용할 수 있다.
        
    return result

result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)

# 파이썬을 사용해서 힙을 사용하게 되면 최소힙 방식으로 힙라이브러리가 구성되어 있기 때문에 우선순위가 낮은 원소부터 꺼내게 됩니다. 따라서 오름차순으로 정렬하고자 한다면 단순히 힙에 모든 자료를 넣어 모든 자료를 빼주면 오름차순 정렬을 이루게 된다. 

 

<힙 라이브러리 사용 예제 코드: 최대 힙>

import heapq

#오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    
    #모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h,-value)
        #부호를 바꿔서 넣어주고 (우선순위가 낮은 것부터 넣어주기 때문)
            
    #힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
        #부호를 바꿔서 꺼내주면 최대힙이 나오게 된다. 
  
        
    return result

result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)