11279 - 최대 힙

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

 

- 최대 힙

 

import sys
input = sys.stdin.readline

from heapq import heappop, heappush

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

for _ in range(n):
    cmd = -(int(input()))

    if cmd:
        heappush(heap, cmd)
    else:
        if heap:
            print(-heappop(heap))
        else:
            print(0)

( heapq를 이용한 최대 힙 구현)

들어오는 값이 자연수일때만 사용 가능

 

import sys
input = sys.stdin.readline

from heapq import heappop, heappush

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

for _ in range(n):
    cmd = int(input())

    if cmd:
        heappush(heap, (-cmd,cmd))
    else:
        if heap:
            print(heappop(heap)[1])
        else:
            print(0)

( heapq를 이용한 최대 힙 구현)

언제든지 사용 가능하다~

 

인자에 튜플을 넣으면 첫 번째 인자로 정렬을 수행한다!

 

import sys
input = sys.stdin.readline

class maxHeap:
    def __init__(self):
        self.heap = []

    def insert(self, n):
        self.heap.append(n)
        index = len(self.heap) - 1

        while index > 0:
            p_index = (index - 1) // 2
            if self.heap[index] > self.heap[p_index]:
                self.heap[index], self.heap[p_index] = self.heap[p_index], self.heap[index]
                index = p_index
            else:
                break

    def remove(self):
        Heap_len = len(self.heap)
        if Heap_len == 0:
            print(0)
            return
        elif Heap_len == 1:
            print(self.heap[0])
            self.heap.pop()
        elif Heap_len == 2:
            print(self.heap[0])
            self.heap[0] = self.heap.pop()
        else:
            print(self.heap[0])
            self.heap[0] = self.heap.pop()
            self.maxHeapify(0)

    def maxHeapify(self, i):
        left_index = 2 * i + 1
        right_index = 2 * i + 2
        max_index = i

        if left_index < len(self.heap) and self.heap[max_index] < self.heap[left_index]:
            max_index = left_index
        if right_index < len(self.heap) and self.heap[max_index] < self.heap[right_index]:
            max_index = right_index
        if max_index != i:
            self.heap[max_index], self.heap[i] = self.heap[i], self.heap[max_index]
            self.maxHeapify(max_index)

    def printHeap(self):
        print(self.heap)


heap = maxHeap()
n = int(input())

for _ in range(n):
    cmd = int(input())

    if cmd:
        heap.insert(cmd)
    else:
        heap.remove()

그리고 클래스로 전체 구현~~