[TIL코테]힙에 대하여

2022-07-05

🚩heap에 대하여

사실 힙이라는 자료구조 또한 엄청 쉬운건데 많이 쓰지 않아서 낯썰었던 것 같다
결론적으로 말을 하면 heap이라는 자료구조는 한마디로 정리하면

매번 정렬!!!

또는

최대,최소 금방 찾아!!!

이렇게 표현할 수 있을 것 같다

애초에 힙이라는 자료구조는 최대/최소를 금방 찾도록 위해 고안된 자료구조로서
각 노드의 key값이 해당 노드의 자식노드의 key값보다 작지 않거나 크지 않은 완전 이진트리이다.

주로 파이썬에서는 최소힙을 제공함으로서 가장 최상단의 노드가 현재 주어진 리스트에 가장 작은값임을 나타낸다.
따라서 어떤 리스트를 힙에 넣게되거나 아님 일부 원소에 수정이 있을 때에도 매번 트리구조로 상단에 최소값이 오는 정렬이 진행이 된다

리스트에 저장될 때에는 각 인덱스의 2idx+1이 왼쪽하단 자식 노드
2idx+2이 오른쪽 하단 자식노드라 생각하면 된다

시간복잡도 O(nlogn)

🔑사용방법

	import heapq
    
    tmp=[3,2,1]
    tmp=heapq.heapify(tmp)
    #주어진 리스트를 힙으로 변환
    
    heapq.heappush(힙변수,넣을려는 노드값)
    #값을 넣어줄때에
    
    min_V=heapq.heappop(힙변수)
    #가장 최상단 노드의 값을 빼준다-즉 최소값을 가져온다

그럼 과연 heap은 문제에서 언제 쓰이는 것 같은지 생각해보면..?

최소/최대를 물어보는데 매번 정렬이 필요하게 되는 상황인 것 같다.
매번 sorted()를 통한 새로운 정렬의 연산비용은 너무 크게 되므로 이럴 때 한 번 heapq를 생각해보자!!

🙋‍♂️그럼 최대힙은 어뜨케..?

파이썬에서는 따로 최대힙을 제공하지 않으므로
부호를 가지고 변환시켜주면 된다

	import heapq
	tmp=[3,2,1]
    h=[]
    result=[]
    
    for x in tmp:
    	heapq.heappush(h,-x)
        #여기서 보면 -음수를 붙여서 반대로 넣어주는 것을 
        #알 수 있다 왜냐하면 -음수를 넣으면 더 작은 값이 
        #앞으로 오는데 해당 숫자를 양수로 보면 더 크기에
    for i in range(len(h)):
    	result.append(-heapq.heappop(h))
      	#다시 부호뒤집어주기
    return result