Heap 힙 개요

힙 자료구조는 완전 이진 트리 그 자체이다.

 

완전 이진 트리 자료구조를 구현 할 수 있다면, 그 구현한 것이 곧 힙 자료구조(우선순위 큐)가 된다.

 

• Heap

완전 이진 트리 (complete binary tree) 형태의 자료구조 이다.

 

1. min heap : 부모 노드의 값이 자식 노드의 값보다 작은 트리 형태의 자료구조

2. max heap : 부모 노드의 값이 자식 노드의 값보다 큰 트리 형태의 자료 구조

 

형제 노드 간에는 대소 관계가 정해지지 않는다.

Root  노드가 가장 큰 값을 갖는다.

 

---

 

일반적으로 모든 요소를 구현 한다면 매우 복잡해 질 것이다.

 

하지만 Linked List로 구현 한다면 ? 저장 및 표현 이 매우 간편해진다.

 

완전 이진 트리를 Linked List로 표현

트리에 인덱스번호를 붙이고 순차적으로 Linked 리스트를 이용하여 다시 표현하였다.

 

단순히 이렇게 표현한다고 하는게 이진 트리와 어떻게 같냐 라고 생각할 수 있지만

 

결론적으로 부모와 자식의 관계만 알 수 있다면 어떻게 표현하든 이진 트리의 원리를 적용할 수 있다는 것

 

아직 와닿지 않지만 예시를 들어 설명하겠다.

 

• 부모 자식 관계를 알 수 있는 방법

 

3의 자식 노드인 7번 노드와 8번노드의 도출 식은

 

 

i = 현재 노드 index

left child index = 2 * i + 1

rihgt child index = 2 * i + 2

 

이 식은 다른 노드에도 동일하게 적용된다.

이 도출식을 이용하면 굳이 완전 이진 트리로 저장하지 않더라도 lift child와 right child 노드를 알 수 있으므로 상관이 없어진다. 

 

반대로 부모의 노드 인덱스도 이러한 공식을 통해 도출 할 수 있다.

Root 노드가 가장 큰(또는 작은) 값을 갖는다.

 

부모노드 : ( i - 1) // 2

 

 

이로써 2진트리를 직접 구현하지 않아도 인덱스를 이용한 계산을 통해 서로의 연결 관계를 알 게 되었다.

 

# heap 구현 및 활용

 

파이썬은 힙 자료구조를 모듈로 제공하여 별도의 구현 없이 바로 사용할 수 있다.

 

import heapq

# min heap 작은 수가 높은 우선순위

min_heap = [5,3,9,4,1,2,6]

heapq.heapify(min_heap)

heapq.heappop(min_heap)

heapq.heappush(1)

# max heap 큰 수가 높은 우선순위

max_heap = [5,3,9,4,1,2,6]

heapq._heapify_max(max_heap)

value = heapq._heapify_max(max_heap)

 

 

 

• heappop()

 

heappop이 이루어지면 가장 우선순위가 높은 노드는 Root

 

Root를 pop() 하고 나면 우선순위에 따라 노드가 바뀌어야한다.

 

이과정을 Shift Down 이라고 한다.

 

- Shift Down 

두 자식노드를 비교하여 우선순위가 높은 노드가 부모 노드가 되도록

자식노드와 부모노드 두 노드를 서로 Swap() 한다.

 

Worst case로 생각해보았을 때 최대 logn(이진트리의 깊이)의 계산 횟수를 가진다

 

결국 Shift Down 계산으로 인해 heappop()의 시간복잡도는 O(logn)

 

 

• heappush()

enqueue 와 같은말 

 

1. 맨 마지막 노드를 추가 O(1)

2. Shift Up 발생 O(logn)

 

- Shift up

부모 노드와 비교하여 우선순위가 높은 노드를 위쪽으로 swap()

shift up 도 마찬가지로  시간복잡도는 O(logn)

 

결국 enqueue와 dequeue모두 O(logn)

 

빅오 log n 은 n보다 더 작은 시간복잡도이기 때문에 매우 효율적

 

log의 특성으로 N이 커질 수록 더욱 효율적이다.

 

heapify(parameter) # 힙을 구성하며 parameter는 리스트 자료형이 올 수 있다.

 

•  max_heap : 큰 수 가 높은 우선순위

1. max_heap 구현 방법

(파라미터의 자료형은 리스트)

heapq._heapify_max(max_heap)

 

2. 두번째 구현방법  각 요소에 - 곱하기

 

min_heap에서 사용했던 heapify 그대로 사용

max_heap의 요소를 -로 사용하여 min_heap을 그대로 사용하지만 결국 max_heap을 사용하는 것과 같게 된다.

 

value 사용시 -를 곱하여 값 그대로 사용

 

3. 세번째 구현 방법

 

 튜플 자료형을 이용하여 기존 요소와 - 요소를 같이 저장

 

heapify는 각 튜플의 0번 인덱스의 값을 활용한다.

 

결국 2번째와 같은 원리이다.

 

heappop() 할 시 weight와 value 두개의 값을 받는다.

 

 

# 코팅 테스트 활용

 

코딩 테스트에선 우선순위큐(힙 자료구조)를 단독으로 사용하는 문제가 나오는 일은 많지 않다.

 

다익스트라 알고리즘을 구현하기 위해서 우선순위 큐가 필요하다. 그래서 heap 자료구조를 이용한다.