힙, 큐 문제풀이

1. 최소 힙 구현하기

• 입력 :
  첫 번째 줄에 힙이 수행할 명령의 수를 나타내는 정수 n을 입력합니다. ( 1≤n≤540000)
  두 번째 줄부터 n개의 줄에 걸쳐 수행할 명령을 입력합니다. 명령의 종류는 다음과 같습니다.
  0 x : 정수 x를 힙에 입력 (0≤x≤5400000 \le x \le 5400000≤x≤540000)
  1 : 힙의 우선순위가 가장 높은 원소 제거
  2 : 힙의 우선순위가 가장 높은 원소 조회

class PriorityQueue:
    '''
    우선순위 큐를 힙으로 구현합니다
    '''
    def __init__(self) :
        self.data = [0]
    def push(self, value) :
        '''
        우선순위 큐에 value를 삽입합니다.
        '''
        self.data.append(value)
        index = len(self.data)-1
        # 마지막으로 삽입한 값이 루트노드가 되면 반복문 종료
        while index !=1:
            if self.data[index//2]>self.data[index]:
                temp = self.data[index]
                self.data[index] = self.data[index//2]
                self.data[index//2]=temp
                index = index//2
            else:
                break

    def pop(self) :
        '''
        우선순위가 가장 높은 원소를 제거합니다.
        '''
        if len(self.data) == 1:
            return
        # 마지막 노드를 루트 노드 자리로 이동한다.
        self.data[1] = self.data[-1]
        self.data.pop()
        index =1
        #[0,1,2,3,4]
        while True:
            # 1. 아무자식도 없는 경우.
            if len(self.data)-1<index*2:
                break
            # 2. 왼쪽 자식만 있는 경우
            elif len(self.data)-1<index*2+1:
                priority = index *2
            else:
                if self.data[index*2] < self.data[index*2+1]:
                    priority = index*2
                else:
                    priority = index*2+1
            if self.data[index] > self.data[priority]:
                temp = self.data[index]
                self.data[index] = self.data[priority]
                self.data[priority] = temp

                index = priority
            else:
                break

    def top(self) :
        '''
        우선순위가 가장 높은 원소를 반환합니다. 만약 우선순위 큐가 비어있다면 -1을 반환합니다.
        '''
        if len(self.data) == 1 : 
            return -1
        else:
            return self.data[1]

1-1. 최소 힙 구현하기(heapq)

import heapq

class PriorityQueue:
    '''
    우선순위 큐를 힙으로 구현합니다
    '''
    def __init__(self) :
        self.data = []

    def push(self, value) :
        heapq.heappush(self.data, value)

    def pop(self) :
        if len(self.data) > 0:
            heapq.heappop(self.data)

    def top(self) :
        if len(self.data) == 0:
            return -1
        else:
            return self.data[0]

2. 최대 힙 구현하기

import heapq

class PriorityQueue:
    
    def __init__(self) :
        self.data = []

    # 루트노드에 -value가 들어감.
    def push(self, value) :
        heapq.heappush(self.data, -value)

    def pop(self) :
        if len(self.data) > 0:
            heapq.heappop(self.data)

    # 아까 push에 붙였던 value에 -를 다시 떼어줘야함.
    def top(self) :
        if len(self.data) == 0:
            return -1
        else:
            return -self.data[0]

3. 절댓값 힙 구현하기

• 이번에 구현할 힙은 절댓값 힙입니다. 즉 원소의 절댓값이 작을수록 우선순위가 높습니다.
  절댓값이 같은 값이 2개 이상 있다면, 가장 작은 수의 우선순위가 더 높다고 계산합니다.
• 코드 :

import heapq

class PriorityQueue:
    
    def __init__(self) :
        self.data = []

    def push(self, value) :
        # abs는 대소비교용, 실제 값은 출력용
        heapq.heappush(self.data, (abs(value), value))

    def pop(self) :
        # 길이를 조사해서 0 이상인 경우만 pop을 하겟음.
        if len(self.data) > 0:
            heapq.heappop(self.data)

    def top(self) :
        if len(self.data)==0:
            return -1

        else:
            return self.data[0][1]

4. 힙정렬 구현하기

• n개의 숫자가 주어질 때, 이를 오름차순으로 정렬하는 프로그램을 작성하세요. 단, 우선순위 큐를 이용하여 구현하도록 합니다.
• 입력값 첫 번째 줄에 n개의 숫자가 공백으로 구분되어 주어집니다.
• 결과값 첫 번째 줄에 n개의 숫자를 정렬한 결과를 출력합니다.
• 코드 :

import heapq

class PriorityQueue:

    def __init__(self) :
        self.data = []

    def push(self, value) :
        heapq.heappush(self.data, value)

    def top(self) :
        if len(self.data) == 0:
            return -1
        else:
            return self.data[0]

    def pop(self) :
        if len(self.data) > 0:
            heapq.heappop(self.data)


def heapSort(items) :
    '''
    items에 있는 원소를 heap sort하여 리스트로 반환하는 함수를 작성하세요.

    단, 이전에 작성하였던 priorityQueue를 이용하세요.
    '''
    # 결과의 정렬된 배열
    result = []

    pq = PriorityQueue()

    for item in items:
        pq.push(item)

    for i in range(len(items)):
        result.append(pq.top())
        pq.pop()

    return result

5. 점토놀이

• n개의 점토를 하나의 덩이로 합치기 위해 필요한 힘의 크기의 합의 최솟값을 구하는 프로그램을 작성하세요.
  만약 무게가 a인 점토와 무게가 b인 점토를 한 덩이가 되도록 합치기 위해서는 a+b의 힘을 들여야 합니다.
• 입력
  첫 번째 줄에 점토의 개수 n이 입력됩니다. (1≤n≤100,000)
  두 번째 줄에 각 점토의 무게를 의미하는 n개의 정수가 공백으로 구분되어 입력됩니다. (1≤점토의 무게≤1,000,000)
• 코드

import heapq

def getMinForce(weights) :
    '''
    n개의 점토를 하나로 합치기 위해 필요한 힘의 합의 최솟값을 
    반환하는 함수를 작성하세요.
    '''
    # 얘를 heap처럼 사용하겠다.
    pq = []

    #heapq.heappush()

    for w in weights:
        heapq.heappush(pq, w)
        
	# 모든 무게를 합치는데 드는 힘.
    result = 0

    while len(pq) > 1:
    	# 1, 2번째로 가벼운 점토들을 x, y에 넣음
        x = heapq.heappop(pq)
        y = heapq.heappop(pq)
		
        temp = x +y
        result = result + temp

        heapq.heappush(pq, temp)

    return result

6. 중간값 찾기

• 입력
  첫 번째 줄에 입력될 수의 개수를 나타내는 정수 nnn이 주어집니다. (2≤n≤150,000)
  두 번째 줄에 n개의 정수가 공백으로 구분되어 입력됩니다.
  입력되는 n개의 정수들을 x라고 할 때, −5,000≤x≤5,000을 만족합니다.
• 출력
  n개의 정수가 차례대로 주어질 때, 매 순간마다의 중간값을 리스트로 담아 반환하는 find_mid 함수를 작성하세요.
  입력된 수의 개수가 짝수라면 중간값이 2개입니다. 이러한 경우에는 더 작은 값을 저장하세요.
• 코드

import heapq

def find_mid(nums) :
    '''
    n개의 정수들을 담고 있는 배열 nums가 매개변수로 주어집니다.
    nums의 각 정수들이 차례대로 주어질 때, 매 순간마다 
    "지금까지 입력된 수 중에서 중간값"을 리스트로 저장하여 반환하세요.
    '''

    n = len(nums)

    result = []

    l = [] # left를 최대 힙으로 쓰겠다.
    r = [] # right를 최소 힙으로 쓰겠다.

    for i in range(n):
        x = nums[i]

        # l또는 r이 비어있는 경우
        if not i or not r:
            heapq.heappush(l, -x)
        else:
            if x >= -l[0]: 
                heapq.heappush(r, x)
            else:
                heapq.heappush(l, -x)

        # 두 힙의 크기를 조정
        # l과 r이 갖고있는 자료의 개수는 같아야 하며, 
        # 총 자료의 개수가 홀수라면, l이 하나 더 많이 들고있게 한다.

        while not (len(l) == len(r) or len(l) == len(r)+1 ):
            # 크기 조정

            #l이 들고있는 개수가 r의 개수보다 2개 이상이다.
            if len(l) > len(r):
                # l에서 값을 뽑아봐서 r에 넣어준다.
                heapq.heappush(r, -heapq.heappop(l))
            
            # r이 l보다 많이 갖고있는 경우
            else:
                # r에서 값을 뽑아봐서 l에 넣어준다.
                heapq.heappush(l, -heapq.heappop(r))

        result.append(-l[0])

    return result