[白俊]7662:双優先級行列

1609 ワード
アルゴリズム#アルゴリズム# テキストリンク

優先キュー


にじゅうゆうせんれつ

重要な問題:オンサイトサービスと同期
二重優先キューなので、最大ヒップと最小ヒップを使用し、Dが1の場合は最大ヒップから、-1の場合は最小ヒップから削除します.しかし、この場合に必要なのは同期です.最大お尻から削除したものは、最小お尻でも同様に削除します.そのために必要なのはアクセス処理です.
import sys
import heapq
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	max_heap = []
	min_heap = []
	visited = [False] * n 
    # 
	for i in range(n):
		x, y = input().split()
		if x == 'I': # 집어넣고, 해당 수 방문 처리 
			heapq.heappush(min_heap, [int(y), i])
			heapq.heappush(max_heap, [-int(y), i])
			visited[i] = True # 이 수는 최소힙, 최대힙에 모두 있다. 
		else:
			if int(y) == 1:
            			# 최대힙이 있다면 최대힙 삭제 , 그리고 삭제한 수는 이제 삭제해야함 
            			# 최소힙에서 방문한 수는  최대힙에서도 그 숫자 삭제해주기 
				while max_heap and visited[max_heap[0][1]] == False:
					heapq.heappop(max_heap)
				if max_heap:
					visited[max_heap[0][1]] = False
					heapq.heappop(max_heap)
			else:
				while min_heap and visited[min_heap[0][1]] == False:
					heapq.heappop(min_heap)
				if min_heap:
					visited[min_heap[0][1]] = False
					heapq.heappop(min_heap)
     	# 모두 다 삭제 됐다면 'EMPTY'출력
	if True not in visited:
		print('EMPTY')
       #여기서도 마지막으로 동기화해주고
       # 최대, 최소 값 출력
	else:
		while max_heap and visited[max_heap[0][1]] == False:
			heapq.heappop(max_heap)
		while min_heap and visited[min_heap[0][1]] == False:
			heapq.heappop(min_heap)
		print(-max_heap[0][0], min_heap[0][0])
[Javascript選択Sort(選択ソート)実装コード
特定の語のみを置換[MySQL]