HEAP

우선 순위 큐는 데이터에서 우선 순위가 높은 데이터 순으로 순차적으로 먼저 뽑는 자료구조입니다. 

리스트로도 충분히 구현할 수 있지만, 문제는 삽입 시간 대비 삭제 시간이 너무 커 효율적이지 못합니다. 

(여기서 리스트는 넣고, 찾고자 하는 조건의 원소를 원소별로 모두 비교하여 삭제하는 방법입니다.)

이에 따라 원소를 삽입할 때는 $\log N$의 시간이 걸리지만 대신에 찾고자 하는 조건의 원소(가장 큰 수, 가장 작은 수)를 찾는 것도 $\log N$으로 해결할 수 있는 자료구조 힙을 사용합니다. 

 

힙은 기본 지식이 없는 상태에서 구현으로 떠올리기 어려운 알고리즘입니다. 이는 힙의 동작의 철학(삽입 혹은 제거 과정에서 원하는 조건을 한번에 처리하는 것이 아니라, 삽입 제거 2가지 과정이 서로 상호보완) 자체가 직관적이지 않기 때문입니다. 

해당 글에서는 직관적이지 않은 두 관계에 집중해서 글을 작성했습니다. 

 

힙에서는 단순히 N개의 데이터를 힙에 넣었다가 꺼내는 과정 자체가 정렬입니다. (힙 정렬)

이 때 시간 복잡도는 $N\log N$입니다. 

 

힙은 완전 이진 트리 자료구조의 일종입니다. 

루트 노드(root node)를 기준으로 루트노드가 가장 작은 값을 갖으면 최소 힙, 가장 큰 값을 가지면 최대 힙입니다.

 

최소 힙(mini heap)

루트 노드가 가장 작은 값을 갖는 경우 

 

최대 힙(max heap)

루트 노드가 가장 큰 값을 갖는 경우

 

최소힙을 예시로 살펴봅시다. 

다음의 예시를 살펴보면 각각의 서브 트리의 루트 노드가 가장 작은 값을 갖는 최소 힙임을 알 수 있습니다. 

 

즉, N 개의 데이터를 트리구조에 넣고, 추후 빼기만 하여도 오름차순으로 정렬됩니다

 

최대 힙은 정반대로, 넣고 빼면 결과로 내림차순으로 정렬되는 것을 알 수 있습니다. 

 

결론적으로 정리하자면, 

완전 이진 트리를 생성하면서, 새로 생성되는 노드와 부모 노드의 우선순위를 비교하여 조건을 만족하면 자리를 교체하는 방식으로 구현할 수 있습니다. 

새로 생성되는 노드는 루트부터 비교하며 내려갈 수도 있고, 반대로 아래부터 위로 거슬러 올라갈 수도 있습니다. 

힙 생성 과정에서 주의할 점은 한가지입니다. 

모든 부모노드가 자식 노드보다 우선순위가 높아야 하고, 자식 노드들간의 관계는 중요하지 않습니다. 

다음과 같은 상황도 발생할 수 있습니다.  (같은 항렬의 부모노드와 자식노드간의 관계 또한 고려 하지 않습니다.) 

 

※가장 이해가 안 갈 수 있는 부분은 바로 heap에서 원소를 제거하는데 걸리는 시간이 $log N$이라는 것입니다. 

root 노트의 제거는 한번이면 가능한데, 왜 $log N$이 걸릴까요? 

이는 바로 제거로 끝나는 것이 아니라 바로 제거 후 최단 노드를 방금 root 노드를 제거한 자리에 넣고 다시 한번 원소 삽입의 과정을 진행하기 때문입니다. 

이 과정을 통해 힙 구조의 완벽하지 않은 형태(같은 항렬의 부모노드와 자식노드간의 관계 또한 고려 X)를 보완합니다. 

 

 

원소 삽입 과정입니다. 

왼쪽 그림의 경우 4번 노드가 트리의 끝부분에 추가가 된 후, 부모인 5번 노드와 대소비교를 한 후 위치를 변경합니다. 5번 노드와의 비교를 마쳤으면 끝입니다. 

오른쪽 그림의 경우 트리에 추가된 2번 노드가 9번 노드와 대소비교를 한 후, 3번 노드와 대소비교를 하여 root의 자리까지 위치 교환을 한 결과입니다. 

이 과정을 통해 결국 모든 노드들은 "부모" 노드로 이어져 있음으로 지금은 투입노드와 부모 노드간의 관계만 정리를 하고, 자식 노드간의 관계는 추후 원소 삭제에서 부모 노드(우선순위 원소)가 삭제 될 때 재 비교를 해서 정립한다는 아이디어를 파악할 수 있습니다. 

 

List에서 힙 생성 하는 방법은 list의 원소들을 heap에 넣어주면 됩니다. 

 

원소 제거 과정입니다. 

 

원소 제거 과정입니다. 

최소 힙에서 root 노드인 2번 노드가 제거되었습니다. 문제는 자식 노드들간의 관계를 알 수 없습니다. 그럼에도 불구하고 알 수 있는 것은 최소한 root 노드가 갖는 두개의 sub 트리의 부모 노드 중에 한 노드가 새로운 최소 값이라는 점입니다. (sub 트리의 하위 값들은 부모 노드보다 우선 순위가 떨어지므로)

이에 따라 최단 노드를 부모 노드에 넣고 자식 노드 두개 중 최종적으로 더 작은 값을 root 노드에 새로운 노드로 올려놓습니다. 그 후 9번 노드를 아래로 내리는 과정을 통해서 자리를 찾아갑니다.

 

 

 

 

이 두 원소 삽입 과정과 제거과정이 정렬에 필요한 과정을 나눠서 수행함으로써 효율적으로 투입, 정렬, 제거를 마칠 수 있습니다. 

 

 

가장 작은 2번 째 숫자를 가져오라와 같은 특정한 상황에서는 모든 데이터를 일단 정렬하고나서 처리하는 것이 아니라, 삽입을 마친 후, 2번의 제거 과정만을 거쳐도 원하는 값을 찾을 수 있다는 점에서 굉장히 효율적입니다. 

 

먼저 파이썬 모듈을 사용하면 다음과 같이 간단하게 사용 가능합니다. 

    import heapq
    heap = [] 
    # 노드 추가
    heapq.heappush(heap, 1)

    # 노드 삭제 (root 노드 return)
    heapq.heappop(heap) 

    # 기존 리스트를 힙으로 변환
    heapq.heapify(tmp)

최대 힙 

    heap_items = [1,3,5,7,9]
    max_heap = []

    #heapify 과정이 push 과정이므로 
    #-item로 최소힙을 구했다고 생각하면 된다. 
    #추후 pop 을 통해 얻은 value[1] 이 우리가 찾는 타겟값! 
    for item in heap_items:
      heapq.heappush(max_heap, (-item, item))

 

직접 구현해보며 과정을 살펴봅시다. 

 

단, 해당 구현은 모든 예외 케이스를 고려하지 않고 흐름만 살려서 구현했습니다. 

class minHeap():
	def __init__(self, lst):
    	self.lst = lst 
   
   	def heapify(lst):
    	heap = [None] + lst[0]
        for i in lst[1:]:
        	heap = heappush(heap, i)
    
    def heappush(heap, val):
    	heap.append(val)
        len(heap)
        while(heap[idx-1] < heap[idx//2] and idx != 0) :
        	heap[idx//2], heap[idx-1] = heap[idx-1], heap[idx//2]
            idx = idx//2
        return heap  	
    
    def heappop(heap):
    	if not len(heap) > 1:
        	print("nothing to pop")
        	return 
    	out = heap.pop(1)
        heap.inset(1, heap.pop(-1))
        idx = 1
        while( and idx != len(heap)):
        	if heap[idx] < heap[idx*2-1] or heap[idx] < heap[idx*2]:
                if heap[idx*2-1] < heap[idx*2]:
                    heap[idx], heap[idx*2-1] = heap[idx*2-1], heap[idx]
                    idx = heap[idx*2-1]
                elif:
                    heap[idx], heap[idx*2] = heap[idx*2], heap[idx]
                    idx = heap[idx*2]
             else:
                  return heap
        return heap

 

 

힙을 직접 사용한 예제 문제를 풀어봅시다. 

프로그래머스의 "더 맵게" 문제입니다. 

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

import heapq

def solution(s, K):
    heapq.heapify(s)
    
    a, answer = heapq.heappop(s), 0 
    while(a < K):
        if len(s) == 0: return -1 
        else:
            answer += 1 
            b = heapq.heappop(s)
            c = a + b*2
            a = heapq.heappushpop(s, c)        

    return answer