우선 순위 큐를 위하여 만들어진 자료구조.
자료구조 | 삭제되는 요소 |
---|---|
스택(Stack) | 가장 최근에 들어온 요소 |
큐(Queue) | 가장 먼저 들어온 요소 |
우선순위 큐(Priority Queue) | 가장 우선순위가 높은 데이터 |
우선순위 큐의 이용 사례
a. 네트워크 트레픽 제어
b. 시뮬레이션 시스템
c. 운영 체제에서의 작업 스케줄링
d. 수치 해석적인 계산
최대 힙(max heap)
최소 힙(min heap)
왼쪽 자식의 인덱스 = 부모의 인덱스 * 2
오른쪽 자식의 인덱스 = 부모의 인덱스 * 2 + 1
부모의 인덱스 = 자식의 인덱스 / 2
다음 세 가지 규칙을 이용해서 구현
class MaxHeap:
def __init__(self):
self.data = [None]
def insert(self, item):
self.data.append(item)
i = len(self.data) - 1
while i > 1:
if self.data[i] > self.data[(i // 2)]:
self.data[i], self.data[(i // 2)] = self.data[(i // 2)], self.data[i]
i = i // 2
else:
break
def remove(self):
if len(self.data) > 1:
self.data[1], self.data[-1] = self.data[-1], self.data[1]
data = self.data.pop(-1)
self.maxHeapify(1)
else:
data = None
return data
def maxHeapify(self, i):
left = 2*i
right = 2*i+1
largest = i
if left < len(self.data) and self.data[i] < self.data[left]:
largest = left
if right < len(self.data) and self.data[largest] < self.data[right]:
largest = right
if largest != i:
self.data[i], self.data[largest] = self.data[largest], self.data[i]
self.maxHeapify(largest)
class Heap:
def __init__(self):
self.data = [None]
def insert(self, item):
self.data.append(item)
i = len(self.data) - 1
while i > 1:
if self.data[i] < self.data[(i // 2)]:
self.data[i], self.data[(i // 2)] = self.data[(i // 2)], self.data[i]
else:
break
def remove(self):
if len(self.data) > 1:
self.data[-1], self.data[1] = self.data[1], self.data[-1]
data = self.data.pop()
self.min_heapify(1)
else:
data = None
return data
def min_heapify(self, i):
left = 2 * i
right = 2 * i + 1
smallest = i
if left < len(self.data) and self.data[i] > self.data[left]:
smallest = i
if right < len(self.data) and self.data[left] > self.data[right]:
smallest = i
if smallest != i:
self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
self.min_heapify(smallest)