👯Priority Queue(feat. Binary Heap)

intro

👯 우선순위 큐 = '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조'

 

👯 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 예를 들어 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우, 즉 가치라는 우선순위에 따라 처리할 때 우선순위 큐라는 자료구조 사용. 앞서 배운 스택의 경우 가장 나중에 삽입된 데이터가 먼저 추출되고, 큐의 경우 가장 먼저 삽입된 데이터가 먼저 추출된다. 하지만 우선순위 큐는 직접 정한 우선순위에 따라 추출되는, 즉, 큐라는 자료구조에서 우선순위라는 어떤 기준을 정해 이에 의해 데이터를 추출하는 방식이라 생각하면 된다.  

 

👯 우선순위 큐는 크게 두 가지 방법으로 구현 가능하다. ① 단순히 list로 구현하는 방법과 ② heap을 이용하여 구현하는 방법이 존재한다. heap의 경우, heap을 사용해서, 단순히 먼저 들어오거나 나중에 들어온 순서가 아닌, 우선순위가 높은, 즉 최댓값 먼저, 아니면 최솟값 먼저 뽑을 수 있는 자료구조를 이용해 효율적인 시간 효율 내로 연산 진행이 가능하다.

 

👯 우선순위 큐를 구현하는 방식에 따른 구현 시간 복잡도 비교 (데이터 개수 N)

우선순위 큐 구현 방식	삽입 시간	삭제 시간
Priority Queue list	O(1)	O(N)
Priority Queue heap	O(logN)	O(logN)

 

① list의 경우 삽입은 단순히 뒤쪽에 삽입하면 되므로 O(1)이지만, 삭제한다면 우선순위가 높은 데이터를 찾아야 하므로 O(N)의 시간이 걸림

② heap의 경우 삽입과 삭제 모두 최악의 경우에도 O(logN)을 보장한다. 따라서 heap에 N개의 데이터를 넣었다가 우선순위로 최댓값 먼저 꺼내거나, 최솟값 먼저 꺼내는 작업은 곧 정렬을 뜻하고, 이는 heap sort라고도 부르며, 당연히 priority queue 삭제 시간 복잡도는 O(logN)이므로 heap sort time complexity는 O(NlogN) (앞선 병합정렬과 시간복잡도 동일)

2. heap 요약

☝️ heapq python library를 사용하자면,

 

→ find max()는 list의 indexing 사용 후, heapify() 함수 사용
(또는 heappop()을 사용하면 알아서 최상단 node를 빼주고, heapify()까지 진행)

 

→ insertion은 heappush() 사용 (알아서 max 또는 min heap 형성)

 

→ heapsort()는 별도 정렬 포스팅 참조 (heappush()와 heappop()을 여러 번 쓰면 된다)

examples

👨‍🏫 python에서 heapq라는 library를 지원해주어 heap 여러 implementation을 쉽게 구현할 수 있다.

 

👨‍🏫 python의 heapq는 default로 min-heap을 구현한다.

Q. heapsort using min-heap

import sys
import heapq
input=sys.stdin.readline
def heapsort(iterable):
    h=[]
    res=[]

    #모든 원소를 차례대로 heap에 삽입
    for value in iterable:
        heapq.heappush(h,value)
    
    #heap에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        res.append(heapq.heappop(h))
    return res

n=int(input())
arr=[]

for i in range(n):
    arr.append(int(input()))

res=heapsort(arr)

for i in range(n):
    print(res[i])

 

1) heapq의 heappush에 의해 min-heap 완성

2) min-heap이므로 heapq의 heappop에 의해 가장 마지막 node가 root node에 오면서 root node인 최솟값이 출력

3) 위 2)의 과정을 계속 반복하면서 출력되는 값을 나열하면 오름차순 정렬!

 

→ 수를 차례대로 집어넣으면, 오름차순 정렬대로 출력되어 나온다.

 

※ python의 경우 heapq는 min-heap 최소 힙을 구현해주는 library다. 따라서 오름차순으로 정렬된다 ※

Q. heapsort using max-heap

※ max-heap은 python의 경우 위 min-heap 구현 코드에 heappush 사용시 value에 음수를 붙여 heap에 집어넣고, 정렬한 뒤, heappop 사용할 때 다시 음수를 붙이면 된다.

import sys
import heapq
input=sys.stdin.readline
def heapsort(iterable):
    h=[]
    res=[]

    #모든 원소를 차례대로 heap에 삽입
    for value in iterable:
        heapq.heappush(h,-value)
    
    #heap에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        res.append(-heapq.heappop(h))
    return res

n=int(input())
arr=[]

for i in range(n):
    arr.append(int(input()))

res=heapsort(arr)

for i in range(n):
    print(res[i])

Q. building a heap - heapify()

 

→ min-heap(완전 이진 트리)을 실제로 만드는 heapify()는 O(n)의 시간 복잡도. 

import heapq

nums = [9,7,5,3,1]
heapq.heapify(nums)
print(nums) #[1,3,5,9,7]

Q. deletion using heappop() - find the nth smallest

 

① 위 만들어진 heap [1,3,5,9,7]에서

 

② 예를 들어 세 번째 작은 원소를 찾고 싶다면 총 두 번의 heappop() 수행한 뒤 O(1)이 걸리는 nums[0] 연산 수행

heapq.heappop(nums)
print(nums) #[3,7,5,9]

heapq.heappop(nums)
print(nums) #[5,7,9]

print(nums[0]) #5 
#heap의 node 출력

 

→ 세 번째 작은 원소 5 출력!

---

 

 

---

* 출처1) 이코테 2021 https://youtu.be/AjFlp951nz0

* 출처2) heap 소개 유투브 https://youtu.be/Zl07LUsR6P0

* 출처3) heap 총정리 youtube https://youtu.be/TK48r1Dlo4k

* 출처4) heap wiki https://en.wikipedia.org/wiki/Heap_(data_structure) 

* 스택오버플로우 출처) https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity