[자료구조] Heap(힙)

---

우선 순위 큐를 위한 자료구조

 

Heap 이란?

 

Heap 이란 자료구소 형태 중 하나로서 우선순위 큐를 위해 사용한다.

예를 들어 최대값 또는 최소값을 계속 반환해야 할 때 효율적이다.

 

---

import heapq

import heapq

heapq 모듈을 선언하여 힙 자료구조를 사용할 수 있도록 한다.

기본적인 내장 모듈이므로 따로 다운받을 필요는 없다.

 

 

 

heapq.heapify(배열) - 배열을 heap 구조로 변환

heap1 = [1,3,2,6,8,0,6]
heapq.heapify(heap1)
heap1
-----------------------------------
[0, 3, 1, 6, 8, 2, 6]

[1, 3, 2, 6, 8, 0, 6]  --> [0, 3, 1, 6, 8, 2, 6] ?

어떤 원리로 바뀐걸까? 숫자의 크기 순서도 아니고....

 

 

내가 한 경우에는 자식노드가 부모노드보다 작을 때 힙 정렬을 만족하지 않는 것 같다.

1. 2의 자식 노드에 0이 있으니 바꿔준다.
2. 1의 자식 노드에 0이 있으니 바꿔준다.
3. 완성!

 

heap은 두 가지 종류로 나뉜다.

• 최대 힙(Max heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙(Min heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

방금 내가 한 변환은 최소 힙에 해당하는 듯 싶다.

 

 

heapq.heappush(배열, 요소) - 요소 추가하기

heap2 = []
heapq.heappush(heap2, 3)
heapq.heappush(heap2, 5)
heapq.heappush(heap2, 1)
heapq.heappush(heap2, 9)
heap2
----------------------------------
[1, 5, 3, 9]

 

이 경우 또한 알아봐야 할 듯 하다.

3 - 5 - 1 - 9 의 순서로 삽입했지만 출력은 [1, 5, 3, 9] 이다.

 

부모노드 > 자식노드 일 때 두 개의 자식노드 중 부모노드와 바뀌는 것은 더 작은 자식노드이다.

 

 

heapq.heappop(배열) - 요소 삭제하기

heap2 = []
heapq.heappush(heap2, 3)
heapq.heappush(heap2, 5)
heapq.heappush(heap2, 1)
heapq.heappush(heap2, 9)
heapq.heappop(heap2)
heapq.heappop(heap2)
heap2
--------------------------
[5, 9]

[1, 5, 3, 9] 배열에서 가장 작은 원소를 pop! [5, 3, 9]

[5, 3, 9]    배열에서 가장 작은 원소를 pop! [5, 9]

 

 

 

---

[플러스] 힙 정렬

# 힙 정렬
import heapq

def heap_sort(arr):
    heap_arr = []
    for num in arr:
        heapq.heappush(heap_arr, num)
    
    sorted_arr = []
    while heap_arr:
        sorted_arr.append(heapq.heappop(heap_arr))
    return sorted_arr

print(heap_sort([5,2,4,9,0]))
-----------------------------------------------------
[0, 2, 4, 5, 9]