BOJ11286. 절대값 힙

작성일

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

  • C로는 이미 많이 짜봤고, 파이썬으로 바이너리힙을 구현하는 연습을 해본 문제
  • heapq라는 라이브러리는 네이티브로 구현되어 있는건지 이겨내기가 쉽지 않았다. 아래처럼 구현한거에 비해 거의 6배이상 차이가 나는듯.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import os
import sys

heap = [0]

def minh(a, b):
    if abs(heap[a]) < abs(heap[b]) or (abs(heap[a]) == abs(heap[b]) and heap[a] < heap[b]):
        return a
    return b

def push(n):
    heap.append(n)
    pullup(len(heap)-1)

def pullup(idx):
    if idx < 1:
        return
    if idx == minh(idx, idx//2):
        heap[idx], heap[idx//2] = heap[idx//2], heap[idx]
        pullup(idx//2)

def pop():
    if len(heap) == 1:
        return 0
    if len(heap) == 2:
        return heap.pop()
    v = heap[1]
    heap[1] = heap.pop()
    pulldown(1)
    return v

def pulldown(idx):
    x = idx
    if 2*idx+1 < len(heap):
        x = minh(minh(idx, 2*idx), 2*idx+1)
    elif 2*idx < len(heap):
        x = minh(idx, 2*idx)
    if x == idx:
        return
    heap[x], heap[idx] = heap[idx], heap[x]
    pulldown(x)


for i in range(int(sys.stdin.readline())):
    x = int(int(sys.stdin.readline()))
    if x == 0:
        print(pop())
    else:
        push(x)