11279 최대 힙 / 우선순위 큐

 

우선순위 큐

• 우선순위가 가장 높은 요소가 가장 먼저 제거됨

힙 -> 우선순위 큐를  구현하기 위한 자료구조 

• 완전이진트리로서, 최솟값이나 최댓값을 빠르게 찾기 위해 만들어진 자료구조, 반정렬 상태 유지(부모노드값이 자식 노드의 값보다 크거나 작은 상태를 유지)
  • 최소 힙 : 부모 노드 값이 자식 노드 값보다 작거나 같음
  • 최대 힙 : 부모 노드 값이 자식 노드 값보다 크거나 같음
• 인덱스
  • 부모 : 자식 노드 값 / 2
  • 왼쪽 자식 : 부모 노드 값 * 2
  • 오른쪽자식 : 부모 노드 값 *2 + 1
• 삽입 : 가장 마지막 노드에 삽입한 후, 부모 노드와 비교하여 교환
• 삭제 : 가장 크거나 작은 노드이기 때문에 루트 삭제 후, 가장 마지막에 있는 노드를 루트로 올린 후에 자식들과 교환

 

class MaxHeap:
    def __init__(self):
        self.heap = []

    def push(self, value):
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)

    def _heapify_up(self, index):
        parent = (index - 1) // 2 #오른쪽 자식의 경우는 -1을 해주고 2를 나눠줘야 부모가 올바르게 나오므로 1뺌
        if index > 0 and self.heap[index] > self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            self._heapify_up(parent)

    def pop(self):
        if len(self.heap) == 0:
            return 0
        if len(self.heap) == 1:
            return self.heap.pop() #힙에 1개만 있으면 바로 반환

        #1개 이상의요소가 있다면 최상단을 반환 후 가장 마지막에 있는 노드를 루트로 올리고 교환
        max_value = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0) #자식 노드와 비교
        return max_value

    def _heapify_down(self, index):
        leftc = index * 2 + 1 #0인덱스로 넘겨서 1씩 더해줌
        rightc = index * 2 + 2
        largest = index

        #자식이 없는 경우에는 인덱스 초과하므로 앞의 길이 조건 추가
        if leftc < len(self.heap) and self.heap[leftc] > self.heap[largest]:
            largest = leftc
        if rightc < len(self.heap) and self.heap[rightc] > self.heap[largest]:
            largest = rightc

        #루트 노드가 자식노드와 변경되었다면 교환
        if index != largest:
            self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
            self._heapify_down(largest)

heap = MaxHeap()
n = int(input())
input_list = []

for _ in range(n):
    input_list.append(int(input()))

for i in input_list:
    if i == 0:
        print(heap.pop())
    else:
        heap.push(i)