본문 바로가기

알고리즘

힙의 다른 응용: 우선순위 큐 priority queue

최대 우선순위 큐 (maximum priority queue)는 다음의 두 가지 연산을 지원하는 자료구조다. 큐는 먼저 들어간 데이터가 먼저 나오는 선입선출(first in first out) 방식이다.

insert(x): 새로운 원소 x 삽입

extract_max(): 최대값을 삭제하고 반환


최소 우선순위 큐는

insert(x)

extract_min()


max heap을 이용하여 최대 우선순위 큐를 구현


어떤 값을 insert하려면 우선 complete binary tree는 유지하면서 마지막 리프에다 붙인다. 그러나 max heap property를 만족하지 않을 수도 있다. 그러므로 max heap이 되도록 조정이 필요하다.  


max-heap-insert(A,key):

  heap_size = heap_size+1

  A[heap_size] = key

  i = heap_size

  while(i>1 and A[parent(i) < A[i]):

    exchange A[i] and A[parent(i)]

    i=parent(i)


시간 복잡도 : O(logn) , 부모와 비교해서 부모보다 크다면 교환을 하므로 최악의 경우에도 높이만큼 반복하게 된다. full binary tree이면서 삽입 값이 루트까지 가면 최악이 될 것이다. 그래도 시간 복잡도는 높이 즉, logn이다.

A=[50,25,60,13,14,52,53]
key=30
def MHI(A,key):
A.append(key)
child=len(A)-1 #index는 0부터 시작
parent=(child-1)//2 #자식 인덱스에서 1을 빼준 뒤 2로 나눈 몫을 구하면 부모 인덱스가 나옴
while A[parent] < A[child]: #자식이 부모보다 크다면
A[parent],A[child]=A[child],A[parent] #교환
child=parent #한 칸 위로 올라감
parent = (child - 1) // 2 #부모도 한 칸 위로 올라감
print(A)
MHI(A,key)

EXTRACT_MAX()

마지막 노드를 루트와 교환한다. 그럼 최대 값이 마지막 노드로 가게 되는데 그 마지막 노드로 최대값을 구할 수 있다. 그런데 루트의 자리에 마지막 노드에 있던 값이 들어가 있으므로 heapify를 해줘야 한다.


A=[20,10,15,8,7,13,14,2,5,6]
key=15

def HEM(A): #Heap Extract Max
if A is None:print('empty list')
A[0],A[-1]=A[-1],A[0]
print('최대값은: ', A[-1])
#max heapify 해줘야 함.
def MHI(A,key): #Max Heap Insert
A.append(key)
child=len(A)-1 #index는 0부터 시작
parent=(child-1)//2 #자식 인덱스에서 1을 빼준 뒤 2로 나눈 몫을 구하면 부모 인덱스가 나옴
while A[parent] < A[child]: #자식이 부모보다 크다면
A[parent],A[child]=A[child],A[parent] #교환
child=parent #한 칸 위로 올라감
parent = (child - 1) // 2 #부모도 한 칸 위로 올라감
print(A)
HEM(A)
MHI(A,key)


출처 https://www.inflearn.com/course-status-2/

'알고리즘' 카테고리의 다른 글

이진 검색 트리  (0) 2018.02.12
트리와 이진트리  (0) 2018.02.12
힙 정렬 heap sort  (0) 2018.02.05
퀵 소트 quick sort  (0) 2018.02.04
합병 정렬 merge sort  (0) 2018.02.03