1927 - 최소 힙

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

1927번: 최소 힙

 

- 최소 힙

 

import sys
input = sys.stdin.readline

class minHeap:
    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[p_index] > self.heap[index]:
                self.heap[p_index], self.heap[index] = self.heap[index], self.heap[p_index]
                index = p_index
            else:
                break
    
    def remove(self):
        heaplen = len(self.heap)
        if heaplen == 0:
            print(0)
        elif heaplen == 1:
            print(self.heap[0])
            self.heap.pop()
        elif heaplen == 2:
            print(self.heap[0])
            self.heap[0] = self.heap.pop()
        else:
            print(self.heap[0])
            self.heap[0] = self.heap.pop()
            self.minHeapify(0)

    def minHeapify(self, i):
        left_index = 2 * i + 1
        right_index = 2 * i + 2
        min_index = i

        if left_index < len(self.heap) and self.heap[min_index] > self.heap[left_index]:
            min_index = left_index
        if right_index < len(self.heap) and self.heap[min_index] > self.heap[right_index]:
            min_index = right_index
        if min_index != i:
            self.heap[min_index], self.heap[i] = self.heap[i], self.heap[min_index]
            self.minHeapify(min_index)

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

heap = minHeap()
n = int(input())

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

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

 

디미고에서 배운거 토대로 구현했다ㅎ.. 근데 알고보니 heapq 라고 파이썬 내장 모듈로 최소힙이 있었다..!!!

 

다른 사람들이 제출한 코드는 300B 내외인데 내 코드는 1600B라 이상하다고 느꼈는데ㅜ 그래도 한 번 구현해본 것도 나쁘지 않았다

 

import sys
input = sys.stdin.readline

from heapq import heappush, heappop

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)

 

추가로.. 나는 heap을 최솟값이나 최댓값만 찾는 자료구조 이라고 잘못 알고 있어서 굳이 O(nlogn)인 힙을 쓸 필요가 있나? 그냥 min 함수나 for 반복문으로 O(n)인 방법을 쓰는게 낫지 않나? 라고 생각했었다

 

근데 heap은 최솟값 / 최댓값을 가장 큰 값으로 정렬하는 자료구조였다~~

정렬에 의의가 있는 자료구조인걸 알게 되어따