Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- Recsys-KR
- MySQL
- eda
- hackerrank
- 프로그래머스
- pytorch
- 한빛미디어
- 튜토리얼
- TEAM-EDA
- Machine Learning Advanced
- Python
- Semantic Segmentation
- 3줄 논문
- 추천시스템
- Segmentation
- Object Detection
- 스택
- 나는 리뷰어다
- DilatedNet
- TEAM EDA
- 알고리즘
- Image Segmentation
- 코딩테스트
- 나는리뷰어다
- 큐
- 파이썬
- DFS
- 엘리스
- 입문
- 협업필터링
Archives
- Today
- Total
TEAM EDA
[데이터구조] 재귀호출 응용 및 힙 본문
우선순위 큐
우선순위 큐 : 원소를 제거할 시, 가장 우선순위가 높은 원소를 제거 (아래의 예시에서는 5부터 제거되었지만 실제 코드에서는 작은 값이 우선순위가 높다고 가정되어서 작은 값부터 제거됩니다.)
우선순위 큐 : 배열로 구현하기
class priorityQueue:
'''
우선순위 큐를 리스트으로 구현합니다
'''
def __init__(self) :
self.data = [0]
def push(self, value) :
'''
우선순위 큐에 value를 삽입합니다.
'''
self.data.append(value)
def top(self) :
'''
우선순위가 가장 높은 원소를 반환합니다. 만약 우선순위 큐가 비어있다면 -1을 반환합니다.
'''
if len(self.data) == 1:
return -1
else:
return min(self.data[1:])
def pop(self) :
'''
우선순위가 가장 높은 원소를 제거합니다.
'''
if self.top() != -1:
index = self.data.index(self.top())
del self.data[index]
def main():
myPQ = priorityQueue()
'''
테스트를 하고싶으면, 아래 부분을 수정합니다.
'''
myPQ.push(1)
myPQ.push(4)
myPQ.push(3)
myPQ.push(2)
print(myPQ.top())
myPQ.pop()
print(myPQ.top())
myPQ.pop()
if __name__ == "__main__":
main()
우선순위 큐 : 이진 트리를 이용해서 구현하기 (힙)
힙 : 부모의 값이 항상 자식보다 작은 완전 이진 트리
- 부모의 값이 항상 자식보다 우선순위가 높음
- 완전 이진 트리 : 트리에 삽입을 할때, 자식의 개수가 2개씩 꽉꽉 채우도록 삽입되는 형태 (아래의 그림에서 값이 삽입되면 7의 자식노드로 들어가야함)
힙에서 값을 삽입하는 경우
- 힙에 값을 삽입하는 경우 완전 이진트리를 맞추도록 값을 삽입해야 합니다.
- 삽입 후 부모노드와 자식노드간의 우선순위관계가 맞는지 확인해주는 작업이 필요합니다.
- 시간복잡도 : O(logn) - 트리의 높이가 높으면 시간복잡도가 높음 (트리의 원소 개수는 2^n-1이고 이때 n이 높이가 됨)
마찬가지로 그 뒤에 27이라는 값을 삽입하는 경우 아래와 같은 과정을 거치게 됩니다.
한번 이번에는 힙에서 값을 삭제하는 경우에 대해서 살펴보도록 하겠습니다.
- 삭제의 경우 가장 우선순위가 높은 부모노드부터 삭제가 됩니다.
- 이후, 가장 마지막 자식노드를 부모노드에 넣습니다.
- 그리고 자연스럽게 우선순위가 높은 노드가 부모노드로 오도록 조정해주면 삭제가 완료됩니다.
- 시간복잡도 - 트리의 높이가 높으면 시간복잡도가 높음 (트리의 원소 개수는 2^n-1이고 이때 n이 높이가 됨)
우선순위가 가장 높은 부모노드 삭제
마지막 자식노드를 부모노드에 삽입
우선순위가 맞도록 노드의 순서를 조정. 이때 23이 3쪽으로 내려가는 이유는 3의 우선순위가 4보다 더 높기때문입니다.
마찬가지로 이후 하나의 값을 더 제거하는 과정까지 살펴보면 아래와 같습니다.
우선순위 큐는 참고로 정렬에도 활용할 수 있습니다. 우선순위 큐의 pop()
에서는 우선순위가 높은 것부터 나오니, 모든 값을 push
하고 pop
해주면 정렬된 순서로 나오게 됩니다.
우선순위 큐 구현하기 (힙)
class priorityQueue:
'''
우선순위 큐를 힙으로 구현합니다
'''
def __init__(self) :
self.data = [0]
def push(self, value) :
'''
우선순위 큐에 value를 삽입합니다.
'''
self.data.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 top(self) :
'''
우선순위가 가장 높은 원소를 반환합니다. 만약 우선순위 큐가 비어있다면 -1을 반환합니다.
'''
if len(self.data) == 1:
return -1
else :
return self.data[1]
def pop(self) :
'''
우선순위가 가장 높은 원소를 제거합니다.
'''
if len(self.data) == 1:
return
self.data[1] = self.data[-1]
self.data.pop()
index = 1
while True:
priority = -1
# 1 아무 자식도 없는 경우
if len(self.data)-1 < index * 2:
break
# 2 오직 왼쪽 자식만 있는 경우
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 = index * 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:
break
def main():
myPQ = priorityQueue()
'''
테스트를 하고싶으면, 아래 부분을 수정합니다.
'''
myPQ.push(1)
myPQ.push(4)
myPQ.push(3)
myPQ.push(2)
print(myPQ.top())
myPQ.pop()
print(myPQ.top())
myPQ.pop()
if __name__ == "__main__":
main()
우선순위 큐 구현하기 (내장힙)
from heapq import heappush, heappop
class priorityQueue:
'''
우선순위 큐를 힙으로 구현합니다
'''
def __init__(self) :
self.data = []
def push(self, value) :
'''
우선순위 큐에 value를 삽입합니다.
'''
heappush(self.data, value)
def top(self) :
'''
우선순위가 가장 높은 원소를 반환합니다.
만약 우선순위 큐가 비어있다면 -1을 반환합니다.
'''
if len(self.data) <= 0 :
return -1
else :
return self.data[0]
def pop(self) :
'''
우선순위가 가장 높은 원소를 제거합니다.
'''
if len(self.data) <= 0 :
return
else :
heappop(self.data)
def main():
myPQ = priorityQueue()
'''
테스트를 하고싶으면, 아래 부분을 수정합니다.
'''
myPQ.push(1)
myPQ.push(4)
myPQ.push(3)
myPQ.push(2)
print(myPQ.top())
myPQ.pop()
print(myPQ.top())
myPQ.pop()
if __name__ == "__main__":
main()
출처
- Elice Academy | 데이터구조 - 재귀호출 응용 및 힙
'강의 내용 정리 > Elice ' 카테고리의 다른 글
[데이터구조] 트리, 트리순회, 재귀호출 (0) | 2020.12.29 |
---|---|
[데이터구조] 스택, 큐, 해싱 (0) | 2019.09.16 |
[데이터구조] 배열, 연결리스트, 클래스 (0) | 2019.09.13 |