우선순위 큐

우선순위 큐

• 우선순위가 가장 높은(낮은) 원소를 먼저 삭제
• 임의의 우선순위를 가진 원소 삽입 가능
• 무순서 선형 리스트
  • IsEmpty() : O(1)
  • Push() : O(1)
  • Top() : Θ(n)
  • Pop() : Θ(n)

# 우선순위 큐 : 가장 값이 큰 원소부터 제거
class MaxPQ:
    pq = []
    size = 0

    def isEmpty(self):
        if len(self.pq) == 0:
            True
        else:
            False

    def push(self, data):
        self.pq.append(data)

    def top(self):
        max = 0
        
        for x in self.pq:
            if max < x:
                max = x
                
        return max

    def pop(self):
        max = 0
        
        for i in range(len(self.pq)): # i는 index
            if self.pq[max] < self.pq[i]:
                max = i
                
        self.pq.pop(max)

    def all(self):
        print(self.pq)

• 최대 히프 : 최대 트리이면서 완전 이진 트리 (√ 최대트리 : 각 노드의 키 값이 그 자식의 키 값보다 작지 않은 트리)
  • IsEmpty() : O(1)
  • Push() : O(1)
  • Top() : O(log n)
  • Pop() : O(log n)
  • 삽입 후에도 최대 히프 유지 : 새로 삽입되는 원소는 부모 원소와 비교하면서 최대 히프가 되는 것이 확인될 때까지 위로 올라감
  • 삭제 후에도 최대 히프 유지
    1. 루트에서 삭제
    2. 마지막 원소를 제거하고 제거된 마지막 원소와 루트의 왼쪽 자식, 오른쪽 자식 중 큰 값과 서로 교환
    3. 최대 히프가 될 때까지 원소 값을 비교하여 교환

# 최대 히프 - list로 구현
class MaxHeap:

    def __init__(self):
        self.data = None

    def push(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 pop(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
        smallest = i
        if left < len(self.data) and self.data[i] < self.data[left]:
            smallest = left

        if right < len(self.data) and self.data[i] > self.data[right]:
            smallest = right

        if smallest != i:
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
            self.maxHeapify(smallest)

# heapq 사용해서 최대 힙 만들기 : heapq는 최소 힙 지원
import heapq
import sys

numbers = int(input())
heap = []

for _ in range(numbers):
    num = int(sys.stadin.readline())
    if num != 0:
        heapq.heappush(heap, (-num))
    else:
        try:
            print(-1 * heapq.heappop(heap))
        except:
            print(0)