알고리즘) 우선순위 큐, 힙

우선순위가 높은 데이터 순서로 자료를 삭제하는 자료구조

-> 가치가 높은 물건부터 꺼내서 확인하는 등

 

힙

-> 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나

최소힙, 최대힙으로 분류

다익스트라 최단 경로 알고리즘 등 다양한 알고리즘에 사용됨

import heapq


### 최소 힙
def heapsort(iterable):
    h = []
    result = []
    for value in iterable:
        heapq.heappush(j, 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)


### 최대 힙

def heapsort(iterable):
    h = []
    result = []
    for value in iterable:
        heapq.heappush(j, -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)