우선순위 큐/ 힙

우선순위 큐/ 힙

우선순위 큐

일반적인 큐는 FIFO 구조이지만 우선순위 큐는 우선순위가 높은 원소가 먼저 출력되는 추상적 자료형

단순하게 배열로 구성하게 되면 입력에서의 시간 복잡도는 1이지만 출력에서 우선순위가 높은 값이 배열의 끝에 있을 경우 O(n)의 시간 복잡도를 가지게 된다. 이러한 시간 복잡도를 줄이기 위해서 나온 것이 힙이다.

힙

최솟값 또는 최댓값을 빠르게 찾기 위해 고안된 완전 이진 트리

최대 힙 - 부모 노드는 항상 자식 노드보다 큰 값을 갖고 있다

최소 힙 - 부모 노드는 항상 자식 노드보다 작은 값을 갖고 있다

파이썬의 heapq 모듈로 최소 힙을 사용할 수 있으며 최대 힙은 값을 저장할 때 음수로 바꿔주어 구현할 수 있다.

힙의 경우 최악의 경우는 새로운 최솟값이 입력되는 경우이고 루트 노드까지 거슬러 올라가게 된다. 연산 횟수는 자신의 부모 노드랑 비교하면서 올라가기 때문에 트리의 높이와 비례함 따라서 시간 복잡도는 O(logn) 자료의 출력은 루트노드가 바로 반환되며 최악의 경우 마지막값이 최대값인 경우에도 시간복잡도는 O(logn)이 됨.

최소 힙 구현해보기

class PriorityQueue: def __init__(self) : self.data = [0] # 배열로 이진트리를 구성할경우 자식노드는 #부모노드 인덱스 * 2, 부모노드 인덱스 * 2 + 1 인데 0이될경우 *연산이 안됨으로 넣어주는 임의값 def push(self, value) : self.date.append(value) index = len(self.data)-1 # 마지막 노드 인덱스 while index != 1 : if self.data[index//2] > self.data[index]: # 부모노드 값이 자식노드보다 클 경우 temp = self.data[index] #부모노드와 자식노드 값 바꿔주기 위한 임시 저장값 self.data[index] = self.data[index//2] #자식노드는 부모노드 값으로 self.data[index//2] = temp # 부모노드는 자식노드 값으로 index = index//2 #부모노드 인덱스 else : #자식노드 값이 부모노드 값 보다 클 경우 그냥 놔두면 됨 break def pop(self): #값을 지우고 정렬 if len(self.data) == 1 : #더미데이터 0만 있는경우로 아무값이 없다는 뜻 return self.data[1] = self.data[-1] # 루트노드값을 마지막 노드의 값으로 바꿔줌 self.data.pop() #마지막노드 값은 삭제 index = 1 #루트노드 인덱스 while True : priority = -1 #왼쪽으로 갈지 오른쪽으로 갈지 결정할 변수 if len(self.data) - 1 < index * 2 : #자식노드가 없는 경우 break elif len(self.data) -1 < index * 2 + 1 : # 왼쪽 자식노드만 있는 경우 priority = index * 2 #왼쪽 자식으로 이동 else : #왼쪽 자식노드 값과 오르쪽 자식 노드 값중 더 작은 값의 자식 노드 인덱스로 이동 if self.data[index * 2] < self.data[index * 2 + 1] : priority = index * 2 else : priority = inex * 2 + 1 if self.data[index] >self.data[priority] : # 현재 인덱스 값 즉 처음 바꿔준 마지막노드 값이 자식값보다 크다면 바꿔줌 temp = self.data[index] #현재 값을 바꿔 주기 위한 임의값 지정 self.data[index] = self.data[priority] #현재값은 자기 자식의 위치로 self.data[priority] = temp #자식 값은 현재 위치로 이동 index = priority #자식위치로 이동 else : #더이상 값이 자식노드보다 크지 않다면 while문빠져나옴 break def top(self) : if len(self.data) == 1 : return else : return self.data[1]

from http://comgiri.tistory.com/25 by ccl(A) rewrite - 2021-09-26 17:00:43