[heapq] 중앙값

우선순위 큐

• 삽입, 삭제 시간을 O(logN)

Import heapq

삽입

• 기본이 최솟값 정렬이므로 최댓값 정렬을 원할 땐, heapq.heappush( q , (-value,value) ) # 우선순위, 값
• heapq.heappush( q , value )

삭제

• heapq.heappop(q)

리스트 to heapq

• heapq.heapify(list)

활용

• 각각의 점의 위치가 주어질 때 마다 지금까지 주어진 점들 중 x, y의 곱이 가장 큰 경우
• 배열에서 가장 큰 값 출력하고 제거
• heapq와 deque 차이
  • 데크는 양 끝 엘리먼트 삽입 제거가 빠르고, 삽입 시에 정렬하진 않는다.
  • 힙큐는 맨 앞 제거 빠르고 삽입 시에 정렬해준다.
  deque() :
• 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거

중앙값 찾기

수열을 입력받고, 홀수 번째의 원소를 읽을 때 마다 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성해보세요.

아이디어

1. 초기 0번째 원소 = Mid값
2. 현재 중앙 값 보다 작은 숫자로만 구성된 maxheap과 중앙값보다 큰 숫자들로 구성된 minheap
3. 중앙값보다 작은 숫자와 큰 숫자의 개수가 동일해야함
4. 짝수 번째 삽입 차례에는 양쪽 원소 수가 동일하므로 중앙값 그대로 두고, 새로운 값과 mid값만 비교 (mid보다 작으면 왼쪽힙에 삽입, 크면 오른쪽 힙)
5. 홀수 번째 삽입 차례에는 개수가 더 많은 쪽에서 값 꺼냄
6. 꺼낸 값, 지금 들어온 값, 중앙값을 크기 순으로 정렬하여 왼쪽힙, 중앙값 갱신, 오른쪽 힙에 저장
7. 갱신과 동시에 mid값 출력

코드 

import heapq 
import sys
T= int(sys.stdin.readline())
#현재 중앙 값 보다 작은 숫자로만 구성된 maxheap과 중앙값보다 큰 숫자들로 구성된 minheap
#중앙값보다 작은 숫자와 큰 숫자의 개수가 동일해야함 
#새로운 숫자가 추가된 뒤 중앙값은 1.m보다 작은 숫자들 중 최댓값, 2. M, 3. m보다 큰 숫자들 중 최댓갑슈 
#최소힙엔 그대로, 최대힙엔 음수부호 붙여서 
def find_mid():
    #원소 1개일 때 중앙값 출력
    mid = arr[0] 
    print(mid, end=" ")
    left_heap,right_heap=[],[]
    
    
    for i in range(1,n):
        #짝수번째 삽입차례에는 양쪽 원소 수가 동일하므로 중앙값 그대로 두고, 새로운 값과 mid값만 비교 
        if i%2==1:
            if arr[i] < mid:
                heapq.heappush(left_heap,-arr[i]) #최대힙으로 삽입 
            else:
                heapq.heappush(right_heap,arr[i]) #오른쪽에 최소힙으로 삽입 
        
        #홀수번째 삽입 차례에는 개수가 1개 더 많은 쪽에서 값 꺼냄
        else:
            if len(left_heap) > len(right_heap):
                new_cand = -heapq.heappop(left_heap)
            else:
                new_cand = heapq.heappop(right_heap)
        #중앙값, 새 값, 꺼낸 값 중에 가장 작은 값은 왼쪽 힙에, 가장 큰 값은 오른쪽 힙에, 중간값은 갱신 
            nums = sorted([mid, arr[i], new_cand])
            heapq.heappush(left_heap,-nums[0])
            mid=nums[1]
            heapq.heappush(right_heap,nums[2])

            # 홀수 번째의 경우에는 중앙값을 출력해줍니다.
            print(mid, end=" ")

    print()



for _ in range(T):
    n=int(sys.stdin.readline())
    arr= list(map(int,sys.stdin.readline().split()))
    
    find_mid()