오랫만에 글쓴다
heap은 정말 ㅈ같은 구조이다.
여서 설명할 자신이 없으니 그냥 나중에 인터넷 다시한번 찾아본다.
이진트리이며, 배열로 구성되있고, maxheap이므로, 모든 부모는 자식보다 커야한다.
편의를 위해 배열의 첫 번째는 0이다.
먼져 insert는, 배열의 마지막에 삽입한다. 이후, 2씩 나눠주며(몫만취함) –완전 2진트리이므로 2씩나누면 부모임
부모가 자기보다 큰 원소일때까지 바꿔나간다.(아님루트일때만)
힙에서 자료를 빼는것이 조금 까다롭다.
먼져, 루트와 마지막노드를 바꿔준다. 그리고 pop해주면, 일단 빼긴 뺀거다.
그럼 당연히 마지막 노드는 작을것이므로, heapify()를 수행해준다.
heapify()란 루트부터 내려가면서 자신의 자식들과 비교하며 자식보다 자기가 작을 경우엔 위치를 바꾼다 –힙구조를 유지시키는 연산이다
재귀적으로 구현해야한다.
참고로, 자식이 2개라면 두 자식들 중 큰놈과 비교하여 자리를 바꾸는 거다.
제일 ㅈ같은거는, 이미 천재들이 모듈을 만들어놨다.
모듈을 쓰면 내것보다 코드가 4배는 짧고 3배는 빠르다.
괜히 구현해보겠다고 객기부렸다가 2시간동안 뻘짓했다.
- 클래스로 구현 (별치이없음)
import sysinput=sys.stdin.readlineimport heapqclass MaxHeap:
def __init__(self): self.data=[None] def insert(self,item): #삽입
#임시로 마지막에 원소 추가 self.data.append(item)
i=len(self.data)-1 #i가 추가된 아이템임 while i>1:
if self.data[i] > self.data[(i>>1)]: # 만일 추가된 데이터가 부모부다 크다면
self.data[i],self.data[(i>>1)]=self.data[(i>>1)],self.data[i] #둘의 위치를 바꿔준다
i=i>>1 #바꿨으니 부모노드의 값을 가진다 else:
break #만일 추가된 데이터가 부모보다 작으면, 거기가 알맞은 위치이다.
def remove(self): #삭제 if len(self.data)>1: #만일 data가 있다면 [none생각]
self.data[1],self.data[-1]=self.data[-1],self.data[1] #루트와 마지막값을 바꾼다
data=self.data.pop() self.maxHeapify(1) else:
data=0 return data def maxHeapify(self,i):
left=i<<1 right=left+1 smallest=i d=0
if left<len(self.data) and self.data[i]<self.data[left]: #왼쪽자식이 존재하고, 왼쪽자식보다 작다면
smallest=left d=self.data[left]
if right<len(self.data) and self.data[i]<self.data[right] and self.data[right]>d: #오른자식이 존재하고, 이보다 작다면
smallest=right if smallest !=i: #현재노드가 최솟값이 아니면
self.data[i],self.data[smallest]=self.data[smallest],self.data[i]
self.maxHeapify(smallest)h=MaxHeap()n=int(input())for _ in range(n):
x=int(input()) if x==0: print(h.remove()) else:
h.insert(x)- 그냥 배열로 구현
import sysinput =sys.stdin.readlineheap=[0]def add(x): heap.append(x)
idx= len(heap)-1 while idx>1: if heap[idx]>heap[idx>>1]:
heap[idx],heap[idx>>1]=heap[idx>>1],heap[idx] idx>>=1
else: returndef remove(): if len(heap)>1:
heap[1],heap[-1]=heap[-1],heap[1] val=heap.pop()
heapify(1) else: val=0 return valdef heapify(node):
l=len(heap) left=node<<1 right = left+1 max_val=0 if left<l:
if right<l: max_val=[left,right][heap[left]<heap[right]]
else: max_val=left
if max_val and heap[max_val]>heap[node]:
heap[node],heap[max_val]=heap[max_val],heap[node]
heapify(max_val) return for _ in range(int(input())):
x=int(input()) if x==0: print(remove()) else: add(x)- 모듈로 구현
import sysinput=sys.stdin.readlineimport heapqheap=[]
for _ in range(int(input())): num= int(input()) if not num :
if not heap: print(0) else:
print(heapq.heappop(heap)[1]) else:
heapq.heappush(heap,(-num,num))나중에 헷갈리면 인터넷 다시헌번 찾아보자
그리고 모듈을 쓰자