# Topic : Data_Structur_2  _ N번째 큰 수
#
# PyPy 3 : 메모리 초과

import sys

N = int(sys.stdin.readline())

box = list()

for _ in range(N):
  box.extend(list(map(int,sys.stdin.readline().rstrip().split())))

box.sort()
print(box[-5])

# Topic : Data_Structur_2  _ N번째 큰 수
#
# PyPy 3 : 792ms
# 위와는 다르게 live의 크기를 N*2 로 제한하여 수행

import sys

N = int(sys.stdin.readline())

live = [] # 각각의 줄을 순회하며 가장 큰 N개의 숫자를 저장할 list

for n in range(N):
  if n == 0:  # 처음에는 그냥 저장한다.
    live = list(map(int,sys.stdin.readline().rstrip().split()))
  else: # 이후에는 이전 live와 비교하고 sort하여 가장 큰 N개의 list를 live에 저장한다.
    tmp = list(map(int,sys.stdin.readline().rstrip().split())) + live
    tmp.sort()
    live = tmp[N:]

print(live[0])

# Topic : Data_Structur_2  _ N번째 큰 수
#
# PyPy 3 : 732ms

import sys
import heapq

N = int(sys.stdin.readline())

heap = [] 

for _ in range(N):  # 한줄씩 입력 
  nums = list(map(int,sys.stdin.readline().rstrip().split()))

  if not heap:  # 처음 heap이 비어있을 경우 heap 초기화
    for n in nums:
      heapq.heappush(heap,n)
  
  else:
    for n in nums:
      if heap[0] < n: # heap에 들어있는 최소값보다 더 큰값이 들어오면 최소값을 heap에서 빼고 해당 값을 heap에 넣어준다.
        heapq.heappush(heap,n)
        heapq.heappop(heap)

print(heap[0])

우선순위 큐

기존의 큐(FIFO)와 다르게 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

우선 순위 큐를 구현시 조건은 다음과 같다

1. 모든 항목에는 우선순위가 있다
2. 우선 순위가 높은 요소는 낮은 요소보다 먼저 큐에서 제외된다
3. 두 요소의 우선 순위가 같으면 큐의 순서에 따라 제공된다.

우선 순위 큐의 경우 배열, 연결 리스트, 힙으로 구현할 수 있는데 이중 힙 구현이 O(logN) 시간 복잡도를 가져 가장 효율적이다.

heapq 모듈을 사용하여 구현시 (”우선 순위(오름차순)”, “해당 원소”) 형태의 튜플을 원소로 사용하여 우선순위별 정렬을 수행할 수 있다.