[sw정글 2주차] 난 슬플 때, Heap-pop Dance를…

Date: 2022.10.04 Updated: 2022.10.04

📚SW정글 2.7주

🏔힙이란 무엇인가

힙이란 쌓여있는 것이다. 숫자들이 heap(무더기)으로 있는 것이다. heap-dict

🏔힙에대해서 무엇을 더 알아야 할까?

from heapq import heappush, heappop

솔직히 이거 알면 다 안거아님? ㅋㅋ 맞다. 힙을 이해하고 있다면 위의 코드 한줄만 알고있어도 된다.

하지만… 이 글을 읽고나면 추가적으로 다음과 같은 사실들을 알 수 있다.

우선순위큐와 heap과의 차이를 알 수 있다.
다운힙과 업힙의 차이를 알 수 있다.
인큐와 디큐시의 힙정렬에 대해 알 수 있다.
다운힙을 통해 힙을 만드는 법과, 힙정렬을 하는법을 알 수 있다.
힙 빌드를 O(nlogn)보다 빠르게 해낼 수 있다.

🧨우선순위큐와 heap과의 차이

우선순위큐는 뭐고 heap que는 무엇일까? heap과의 차이는 무엇일까? 나도 그렇고 많은 사람들이 우선순위 큐를 공부하면서 Heap에 대해 다시금 공부한다.

우선순위큐(Priority Queue)는 ADT(Abstract Data Type)이다.

그리고

힙(Heap)은 자료구조(Data Structure) 이다.

이게 무슨소리일까? 힙(heap)의 키(key)를 우선순위(priority)로 사용한다면 힙은 우선순위큐(priority queue)의 구현체가 된다는 뜻이다. 조금 더 풀어서 설명 해 보도록 하겠다.

우선순위큐는 구현은 설명하지 않고, 어떻게 동작하는지에 대한 개념설명인 것이다. Priority Queue에는 사실 Heap 말고 여러 구현체들이 있지만, Heap구조가 효율과 성능이 가장 좋기 때문에 자주 쓰게 되고, 그러다보니 우선순위큐는 힙과 같다! 라는 인식이 생긴 것 같다

Heap은 구현까지 있는 것이다. 위에서 설명했듯, priority queue의 구현체라고 많이들 설명한다.

그런 말장난이 어디있냐고 하는 사람들도 있겠지만, 우선순위큐를 heap이 아닌 다른 방법으로도 구현할 수 있다는 정도의 (작은)깨달음을 가져가면 괜찮지 않을까 싶다.

👎다운힙과 👍업힙

down-heap

먼저 다운힙을 설명하고자 한다. 내려가면서 힙을 해주는게 다운힙이라고 한다. 조금 더 자세히 설명 해 보자면, 위의 그림처럼 루트노드에 마지막 노드가 들어오고 자식들과 비교해가며 자기 자리를 찾아간다. 이처럼.. 자식과 비교해서 자리를 찾아 내려가는것을 다운힙(Down-Heap)이라고 한다. 내리는 연산이므로 shift down이라고 표현하기도 한다.

up-heap

그렇다면 업힙은? 반대이다. 부모와의 비교를 계속 해 나가며 자기 자리를 찾아가는것을 볼 수 있으며, 이를 업힙(Up-Heap) 이라고 한다. 올려보내는 연산이므로 shift up이라고 표현하기도 한다.

그렇다면 다운힙과 업힙은 언제 사용하는 것일까? 요소의 삽입과 삭제에 필요하다

⭕️요소의 삽입과 ❌삭제

힙구조를 이루고 있는 데이터에 새로운 요소를 집어넣을 때 업힙을 사용한다. 업힘은 자신의 형과 비교하지 않는다. 그저 올라갈 뿐이다. 내가 부모보다(작거나)크다? 그러면 그냥 올라가는 것이다. 이미 힙구조를 이루고 있기 때문에, 형제 key값이 더 크다고 형이 올라갈 필요가 없는 것이다.

하지만 요소를 빼낼 경우 이야기가 다르다. 루트노드에는 항상 최대값(혹은 최소값)을 가지고 있어야 한다. 이를 위해서는 형제노드중 가장 더욱 큰 값을 올려보내야 하는 것이다. 따라서 다운힙을 구현 할 때에는, 형이 더 큰지 동생이 더 큰지 꼭 비교를 해야 하는 것이다. 그렇지 않으면 제대로된 힙구조를 만들 수 없다.

따라서 다운힙을 구현 할 때에는 고민 할 요소가 많다. 형이 더 큰지 자식이 더 큰지 비교해야하며, 이 값이 부모보다 큰지 다시 비교해아 한다. 자식 key값들을 설정하면서 형과 동생이 모두 있는지, 형만 존재하는지에 대한 체크도 반드시 짚고 넘어가야 한다.(index error)가 나기 일쑤이다.

parent, child = child, parent

요소의 교환은, 파이썬에서 위와같이 간단히 연산해줄 수 있다.

🏔힙빌드의 두가지 방법

Heap구조를 이루고 있는 데이터에 Enque를 해줄 때, 업힙을 통해서 O(logn)의 속도로 데이터를 집어넣어 줄 수 있다. 그렇다면 Heap구조를 이루고있지 않은 배열은 어떻게 처리할까?

일단 이미 존재하는 배열을 Heap구조로 변환시켜주어야 한다. 이러한 과정을 Heapify 혹은 Heap build라고 부른다.

❗️힙빌드의 첫번째 방법

업힙을 이용하는 방법이다. 빈배열에 요소를 하나씩 업힙으로 넣어주는 방법이다. n개의 배열이 있었다면, 업힙을 n번 해주어야 하므로, O(nlogn)의 시간이 걸린다. logn을 n번 연산하는게 아니다. 다음과 같이 logn을 향해 가는 배열들의 합이 nlogn인 것이다.

(0 _ n/2) + (1 _ n/4) + (2 _ n/8) + ... + (h _ 1).

❗️힙빌드의 두번재 방법

많이 헷갈리는 방법이다. 이 방법의 이름은 '상향식 힙빌드'이다. 하지만 업힙을 쓰는게 아니라 다운힙을 사용하는 것이다. 영어 포럼에서는 Heapify shift down method 로 검색을 하면 관련 정보를 얻을 수 있다.

heap-build-prove

위의 그림과 같이 테일러 시리즈를 이용하여, heapify를 하는데 O(n)이 걸림을 알 수 있다. 따라서 무조건 Shift Down으로 heapify를 해야한다.

시간복잡도와 HeapSort

Heapify를 하는데 O(n)이 걸리는데, 왜 Heapsort는 O(nlogn)이 걸리는 것일까? 저번 포스트에서 사람들이 관심없어하는 힙정렬(링크) 에 대해 알아보았다. 이유는 Heapify를 해도, Heap구조를 이루지만 정렬되어있지 않기 때문이다. Heap구조를 만드는 데에 O(n)의 시간이 걸리고, Heap정렬까지 이루는데 O(nlogn) 이 걸린다.

DownHeap 함수를 이용한 Heapify와 Heapsor(Code snippet)

    def down_heap(a:MutableSequence, left:int, right:int) -> None:
        """a[left] ~ a[right]를 힙으로 만들기"""
        temp = a[left]

        parent = left
        while parent < (right+1)//2:
            cl = parent*2 + 1
            cr = cl +1
            child = cr if cr<= right and a[cr] > a[cl] else cl
            if temp >= a[child]:
                break
            a[parent] = a[child]
            parent = child
        a[parent] = temp

    n = len(a)

    """Heapify만 하기"""
    for i in range((n-1)//2, -1,-1):
        down_heap(a,i,n-1)

    """Heap sort까지"""
    for i in range(n-1,0,-1):
        a[0], a[i] = a[i], a[0]
        down_heap(a, 0, i -1)

+위 연산의 총 소요시간은

h*n/2 + (h-1)*n/4 + ... + 0 * 1.

🧸Heap 구현을 마치며

Max-Heap: 크면 => 바꾼다 => 꼭대기에 최대값 Min-Heap: 작으면 => 바꾼다 => 꼭대기에 최소값

생각보다 간단한 개념이다. 하지만, 우선순위큐의 삽입, 삭제를 구현하는데 생각보다 애를 많이 먹었다. 심지어 인터넷에 올라와있는 코드도 잘못된 부분이 많아서 더욱 힘들었다. 과동기인 2wheeh 이를 키메라합성으로 불렀다. 이진트리를 구현하고, Enque와 Dequeue 구현체를 들고와서, 삽입과 삭제 함수에 upheap과 Downheap을 삽입해서 창조해내는 고통스럽고 괴상한 과정이였기 때문이다. 나도 나만의 재료들로 키메라 합성에 도전하였으나 Downheap구현과 몇몇 오개념으로 엄청난 시간을 쏟게 되었다. 우리 A반의 현진이형, 그리고 과동기와 그의 팀원(모르는사람)의 코드가 개념을 이해하는 과정에서 정말 큰 도움이 되었다.

🕺🏾슬플땐… heap-pop dance🕺🏾

😵배우면서 깨달은 내용을 정리해 보았습니다. 오개념을 아래 댓글에 달아주시면 감사하겠습니다😵

🌜 Thank you for reading it. Please leave your comments below😄

맨 위로 이동하기

Sunny Yoon