우선순위 큐(priority queue)와 힙(heap)

1. 우선순위 큐

• 우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 
• 데이터를 우선 순위에 따라 처리하고 싶을 때 사용한다.

예시 ) 물건 데이터를 자료구조에 넣었다가 가치가 놓은 물건부터 꺼내서 확인해야하는 경우

자료구조	추출되는 데이터
스택	가장 나중에 삽입된 데이터
큐	가장 먼저 삽입된 데이터
우선순위 큐	가장 우선 순위가 높은 데이터

 

1.2 우선순위를 구현하는 방법

1. 리스트로 구현

2. 힙을 이용해 구현

 

데이터의 개수가 n일 떄 구현 방식에 따라서 시간 복잡도를 비교한 내용은 다음과 같다. 

우선순위 큐 구현 방식	삽입시간	삭제시간
리스트	O(1)	O(N)
힙	O(logN)	O(logN)

 

n개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. (힙 정렬)

  ->  이 경우 시간 복잡도는 O(NlogN)이다. 

 

 

2. 힙의 특징

힙은 특정한 규칙을 가지는 트리, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로 한다.

• 힙은 완전 이진 트리 자료구조의 일종
• 힙에서는 항상 루트 노드를 제거
• 두가지로 나누어진다. 
  • 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
  • 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙

키 값의 대소관계는 부모/자식 간에만 성립하고 , 형제 노드 사이에는 대소 관계가 정해지지 않는다.

 

2.1 완전 이진 트리

루트 노드부터 시작해 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리.

 

2.2 힙 합수

파이썬에서는 힙 함수를 제공하고 있다. 

 

import heapq

 

1. 힙 생성 : heapq.heapify()

import heapq

arr=[1,4,3,2,5]

heapq.heapify(arr)

 

 

 

  2. 힙 원소 추가 : heapq.heappush(arr,number)

import heapq

heap=[]
heapq.heappush(heap,5)
heapq.heappush(heap,4)
heapq.heappush(heap,7)

print(heap)

>>> [4,5,7]

 

3. 힙 원소 삭제 : heapq.heappop(arr)

 

import heapq

result=heapq.heappop(heap)

print(result)
print(heap)

>>> [4]
>>> [5,7]

 

 

힙 대표 문제

프로그래머스 더 맵게 (level 2)라는 문제가 힙을 사용해서 풀기 딱 좋은 듯 하다. ..

 

프로그래머스

 

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

 

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

#프로그래머스 더맵게
import heapq

def solution(scoville,K):
    heapq.heapify(scoville) #heap형태로 만들어주기
    result=0 #횟수

    while len(scoville)>=2: #힙에 1개만 남으면 더이상 계산 불가하기 때문에 
        min_1=heapq.heappop(scoville) #최소값 추출

        if min_1>=K:#최솟값이 K보다 크면 종료
            return result
        else:
            min_2=heapq.heappop(scoville) #그다음 최소값 추출
            heapq.heappush(scoville,min_1+(min_2*2)) #계산
            result+=1 #횟수 추가

    if scoville[0]>=K: 
        return result 
    else:
        return -1
    

solution([1, 2, 3, 9, 10, 12],7)

 

[3, 5, 10, 12, 9]
1
[9, 12, 10, 13]
2

 

result 1 : 처음에 최솟값 1과 그다음 최솟값 2를 추출해 계산 1+(2*2)=5 -> [3,5,10,12,9]

result 2 : 최솟값 3과 그다음 최솟값 5를 추출해 계산 3+(5*2)=13 -> [9,12,10,13]

 그래서 출력은 2