Binary heap

👨‍🏫 우선순위 큐는 max-heap 또는 min-heap을 사용해 우선순위에 맞는 데이터를 뽑을 수 있는 자료구조임을 공부했다. (아래 포스팅 참조)

 

priority queue - (binary) heap tree

 

☝️ priority queue는 일종의 Abstract Data Structure(ADT)로, 추상화된 개념을 heap이라는 자료구조로 implement할 수 있다.

(우선순위가 최대 먼저, 또는 최소 먼저일 경우 heap은 트리 구조를 만들어 이의 우선순위에 맞게 꺼내준다)

 

👨‍🏫 따라서, 중요 자료구조 heap에 대한 자세한 모든 정보를 정확히 정리해봄

---

👨‍🏫 일단 heap data structure는 여러 형태로 표현될 수 있다. 이 중 Binary heap에 대해 자세히 알아보려 한다.

1. binary heap intro

👨‍🏫 보통 위에서 언급한 priority queue를 구현할 때 많이 쓰임

 

👨‍🏫 binary tree 형태이며, 그 중 complete binary tree 형태를 보인다.

 

👨‍🏫 binary tree는 두 개의 조건 하에 정의된다. → shape property, heap property

* shape property - complete binary tree

👨‍🏫 Complete Binary Tree(CBT; 완전 이진 트리)란, root 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 tree를 뜻한다.

 

'all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.'

 

👨‍🏫 위 그림처럼 왼쪽부터 차례대로 node에 데이터가 채워지고, 맨 아래층을 제외한 모든 층의 node가 채워진다. 단, 마지막 층은 왼쪽부터 node가 채워진다.

 

👨‍🏫 Binary Tree 종류 포스팅 참조

Types of Binary Tree🌲

 

👨‍🏫 따라서, 아래 tree들 중 CBT는 1번, 2번, 5번, 6번이다

 

👨‍🏫 그렇다면, heap property에 의해 나뉘는, heap의 두 종류 max-heap과 min-heap에 대해 알아보자

* heap property - max-heap & min-heap

'Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children, according to some total order.'

 

👨‍🏫 max-heap: parent key가 child keys보다 크거나 같은 heap

 

👨‍🏫 min-heap: parent key가 child keys보다 작거나 같은 heap

 

→ 다시 정리하면,

☝️ 최소 heap(min-heap): root node가 가장 작은 값을 가지며, 값이 작은 데이터가 우선적으로 제거된다.
(이럴 경우 만들어진 최소 heap에 n개의 데이터만 넣어도 자동적으로 오름차순 정렬이 완성된다)

☝️ 최대 heap(max-heap): root node가 가장 큰 값을 가지며, 값이 큰 데이터가 우선적으로 제거된다.

 

※ 따라서, max-heap과 min-heap은 우선순위 큐를 implement할 때, element를 inserting하거나, 가장 작거나 가장 큰 element를 각각 min-heap과 max-heap에서 빼는 이 두 가지 operation에서 효율적이게 많이 쓰인다.

 

※ 또한, heapsort sorting algorithm(in-place algorithm)으로 heap이 쓰인다. 서로 node끼리 상대적으로 위치를 바꾸는 알고리즘이므로 in-place 알고리즘이다.

 

👨‍🏫 예시 (왼쪽은 max-heap, 오른쪽은 min-heap)

2. binary heap implementations

👨‍🏫 heap 구현은linked list와 array 두 구조로 구현이 가능한데, linked list는 많은 메모리 차지,주로 array로 구현된다. array의 index를 이용해 heap binary tree에 쌓는 과정을 알아보자

* child & parent's node (based on the node's index)

※ 상위 node의 index가 i라면

→ root node의 index가 0이면, 하위 left node의 index는 2i+1, 하위 right node의 index는 2i+2

→ root node의 index가 1이면, 하위 left node의 index는 2i, 하위 right node의 index는 2i+1

 

→ 위 array에는 10, 30, 40, 90, 60 순서대로 들어가 있다. root node부터 차례로 왼쪽부터 array에 들어가는데, 만약 자식 node의 index가 x라면

→ root node의 index가 0일 경우 parent node의 index는 $\lfloor \cfrac{(x-1)}{2} \rfloor$

→ root node의 index가 1일 경우 parent node의 index는 $\lfloor \cfrac{x}{2} \rfloor$)

 

👨‍🏫 주어진 array의 원소들을 array 공간을 다시 써서 해당 공간에서 binary heap 형태로 저장하는 heapsort 알고리즘으로 쓰인다.

 

👨‍🏫 위 완성된 binary heap과 array와의 index 순서, array element 순서를 서로 잘 살펴보며 기억하자!

 

👨‍🏫 heap에서 진행되는 여러 과정은 일단 max-heap을 기준으로 한다.

---

* creating a heap

👨‍🏫 그렇다면, heapsort의 core 알고리즘인, 주어진 array를 binary heap 형태로 저장하는 과정을 한 단계씩 자세히 살펴보자

 

* 예시) array [33, 35, 42, 10, 7, 8, 14, 19, 48]이 주어졌다면, 맨 앞의 원소부터 시작. child node로 들어갈 때, parent node와 크기를 비교하고, max-heap일 경우, parent node보다 들어가는 원소가 더 크다면 서로 swap. 다시 상위 parent node와 비교 (min-heap은 parent node보다 원소가 더 작다면 parent node와 swap)

- 그 결과 array [48, 42, 35, 33, 7, 8, 14, 10, 19]인 binary max-heap 완성

 

- 완성된 binary max-heap -

 

👨‍🏫 위 예시 A [33, 35, 42, 10, 7, 8, 14, 19, 48]가 주어졌을 때, 주어진 array를 binary heap에 맞게 바꾸는 heapify를 python으로 구현!

→ 출력하면 A가 [48, 35, 42, 33, 7, 8, 14, 19, 10]로 바뀐다.

 

def heapify(arr, n, parent_idx):
    largest = parent_idx
    left = parent_idx*2 + 1
    right = parent_idx*2 + 2

    if left < n and arr[left] > arr[largest]:
        largest = left
    
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != parent_idx: #if changed
        arr[largest], arr[parent_idx] = arr[parent_idx], arr[largest] #swap
        heapify(arr, n, largest) #if swapped, continue with the lower part

arr = [33, 35, 42, 10, 7, 8, 14, 19, 48]

for i in range((len(arr)-1)//2,-1,-1): #heapify
    heapify(arr, len(arr), i)
    print(arr)

print(arr) #[48, 35, 42, 33, 7, 8, 14, 19, 10]

 

→ heapfiy() 시간 복잡도 O(N) (각 node별 heapify()를 여러 번 시행)

 

▶ time complexity ◀

 

→ 먼저, 총 n개의 node가 있다고 하고, 바닥부터 h=0, 그 다음 층 h=1과 같은 방식으로 진행된다고 가정하면, h라는 층에 존재하는 최대 node 개수는 $\cfrac{n}{2^{h+1}}$

 

→ last non-leaf node부터 root-node까지 각각 max_heapify()가 진행된다. 이 때, max_heapify()에서 swap을 위한 comparison 횟수는 곧 시작 node의 height를 뜻한다. 따라서 우리는 시간복잡도를 h라는 층에서 $O(h) * \lceil\cfrac{n}{2^{h+1}}\rceil$로 나타낼 수 있다.

(O(h)는 시작 node의 height - 즉 일정 상수 $c*h$로 표현 가능)

 

→ 각 모든 층의 시간복잡도를 구하면, n개의 node에서 층의 개수는 logn이므로 $\sum_{0}^{log n}O(h) * \lceil\cfrac{n}{2^{h+1}}\rceil$

= $\cfrac{n*c}{2} \sum_{0}^{logn} \lceil\cfrac{n}{2^h}\rceil$

 

→  logn을 ∞로 바꾸면, harmonic progression에 의해 시그마값은 2가 된다.

= $\cfrac{n*c}{2} * 2$ = $c*n$

 

▶ T(n) = O(n) ◀

 

※ 아래 참조 ※

---

* deleting from heap → heapsort

👨‍🏫 이미 완성된 binary heap에서 한 원소를 delete한 다는 것은, 가장 상위의 root node를 빼 온다는 뜻이고, max-heap일 경우 원소의 최댓값, min-heap일 경우 원소의 최솟값을 가져오게 된다.

 

👨‍🏫 root- node를 빼오고 남은 자리에는, bottom-most right-most element를 빼온다. (array구조상 index가 가장 큰, 맨 오른쪽의 원소). 이를 root node에 올려놓는다.

 

*예시) 위 예시를 그대로 사용하면, 42를 빼고, 10 원소를 맨 위에 올려 놓는다. 이 때, 항상 max-heap 구조를 유지해야 하므로, 새로 바뀐 root-node와 child-node를 비교한다. swap이 진행되면, 이후 아래 부분까지 대소 관계가 max-heap 구조에 맞지 않으면 계속해서 swap 진행

 

- (좌) root node 빼오고 마지막 원소를 root node로 올림 / (우) 최종적으로 swap 과정이 진행된 후 다시 업데이트 된 max-heap -

- update된 max-heap을 array 형태로 표현하면 [35, 33, 14, 19, 7, 8, 10]이 된다.

- 이와 같이 계속해서 root-node deletion을 진행하면 제일 큰 수부터 차례대로 delete된다. 따라서, delete된 원소를 차례대로 모으면, sort된 결과가 나온다. 이 sorting을 heapsort라고 부른다.

(여기서 parent node와 두 child node 중 제일 큰 child와 swap이 진행된다.

left와 swap이후 right와 한 번 더 swap이 진행되는 게 아님)

 

- 아래 코드 heapsort 참조 -

def max_heap(arr, n, parent_idx):
    largest = parent_idx
    left = parent_idx*2 + 1
    right = parent_idx*2 + 2

    if left < n and arr[left] > arr[largest]:
        largest = left
    
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != parent_idx: #if changed
        arr[largest], arr[parent_idx] = arr[parent_idx], arr[largest] #swap
        max_heap(arr, n, largest) #if swapped, continue with the lower part

def heapsort(arr):
    
    n = len(arr)

    for i in range((n-1)//2,-1,-1): #first heapify
        max_heap(arr, n, i)

    for i in range(n-1,0,-1): #heapsort (until last single element remained)
        arr[i], arr[0] = arr[0], arr[i] #swap with the last and the first(max) element
        max_heap(arr,i,0) #after swapped, heapify (start with the first element)

arr = [33, 35, 42, 10, 7, 8, 14, 19, 48]
heapsort(arr)
print(arr) #[7, 8, 10, 14, 19, 33, 35, 42, 48]

 

① max_heap(): arr와 전체 arr 길이, 현재 parent_idx 세 개의 인자

→ 일단 현재 largest index는 parent_idx이고, 자식 node의 index는 parent_index*2 +1과 parent_index*2+2

(IndexError 걱정할 필요 없다. max_heap을 돌릴 때 non-leaf node 까지만 돌리기 때문)

→ 자식 left node가 parent node보다 크다면, 그리고 left node의 index가 n보다 작다면, swap 필요하므로 index swap

→ 이후 자식 right node와도 동일하게 진행

→ 만약 index swap이 진행되었다면(largest != parent_idx)

- arr[largest]와 arr[parent_idx]와의 swap 진행

- 그리고, 이후 아래 하위 노드와도 이를 반복해야 하므로 max_heap(arr, n, largest) 진행

(이 때, parent_idx는 largest이므로, largest를 인자로 넣음)

→ heapify() 시간 복잡도 O(logN)

 

② heapsort()

→ last non-leaf node부터(즉, n개의 node에서 index가 $\lfloor \cfrac{n}{2} - 1 \rfloor$인 node부터) root node까지 차례대로 heapify() 점검

(last non-leaf node란, 자식 노드가 1개 이상 있는 node 중 index가 제일 큰, 즉 array에서 맨 끝에 있는 node를 뜻한다. 즉 자식이 있는 끝 노드부터 root node까지 max-heap 구현을 위해 swap 여부를 자식과 계속 실시한다는 뜻) - for loop 돌림

→ 한 번의 heapify() 진행 후, n번의 heapify() 진행 (for loop 돌림) - 첫번째 원소와 맨 마지막 원소 swap & max_heap() 돌려 heapify() 진행

(한 개 남을 때 까지 진행하므로, index n-1부터 1까지)

 

▶ heapsort T(n) = O(nlogn) ◀

 

→ 각각 max node를 빼오고 매 번 heapify()를 진행해주므로, heapify()의 시간 복잡도는 O(logn)인 상태에서, max node를 빼오는 횟수 n이 최종적으로 곱해져 O(nlogn)의 시간복잡도가 된다.

---

* inserting key into heap

👨‍🏫 이미 완성된 heap에서 맨 마지막에 새로운 원소를 insertion할 수 있다. 이 때, max-heap의 성질을 유지하기 위해 부모 노드 원소와 계속 비교하며 상위로 올라간다. (하단 그림 참조)

👨‍🏫 이처럼, 임의의 binary heap 원소 중 한 개의 값을 바꾼다면, 상위 노드와 계속 비교하면서 max-heap 생성을 위해 swap 과정이 진행될 수 있다.

※ binary heap 특성상 자식 node의 index가 i라면, 부모 node의 index는 i/2 ※

 

def insert_key(arr,key):
    arr.append(key)
    size=len(arr)
    i=size

    while(i>=1 and arr[i/2] < arr[i]):
        arr[i],arr[i/2] = arr[i/2],arr[i] #swap
        i = (i/2)
    print(arr)

 

▶ T(n) = O(h) = O(logn) ◀

(node의 값을 증가시켜 heap을 update하는 연산의 시간 복잡도는 자식 node가 최대 부모 node까지 움직이는, 즉 heap의 height가 되므로, 이는 곧 logn)

---

* extract max from heap

👨‍🏫 지금 max-heap을 다루고 있으므로, heap의 원소 중 최댓값은 가장 상위 노드에 있는 값이다. 따라서 맨 위의 노드를 빼고, 그 자리에 가장 끝에 있는 원소를 갖다 준다. (하단 그림 참조)

 

def delete_max(arr):
    size=len(arr)
    if size < 1:
        print('Error')
    
    max_root = arr[0]
    arr[0] = arr[size]
    size=size-1

    A=max_heapify(arr[:size],1)
    return max_root

 

👨‍🏫 max값을 반환하고, 마지막 원소를 root node로 올린 뒤, max_heapify()를 사용해 max-heap으로 다시 만든다.

 

▶ T(n) = O(logn) ◀

(max_root를 최상위 node에서 꺼내는 건 O(1), max_heapify()는 O(logn)으로 최종 O(logn))

---

* increase key in heap

👨‍🏫 예시) 맨 마지막 rightmost node 값을 60으로 바꾼다면 max-heap 성질에 의해 상위 노드 42와 비교해서 swap, 이후 상위 노드 48과 비교해서 swap 진행 (아래 그림 참조)

👨‍🏫 이처럼, 임의의 binary heap 원소 중 한 개의 값을 바꾼다면, 상위 노드와 계속 비교하면서 max-heap 생성을 위해 swap 과정이 진행될 수 있다.

※ binary heap 특성상 자식 node의 index가 i라면, 부모 node의 index는 i/2 ※

 

def increase_key(arr,i,key):
    if key < arr[i]:
        print('Error')

    arr[i] = key
    while(i>=1 and arr[i/2] < arr[i]):
        arr[i],arr[i/2] = arr[i/2],arr[i] #swap
        i = (i/2)
    print(arr)

 

▶ T(n) = O(h) = logn / S(n) = 1◀

→ node의 값을 증가시켜 heap을 update하는 연산의 시간 복잡도는 자식 node가 최대 부모 node까지 움직이는, 즉 heap의 height가 되므로, 이는 곧 logn / 공간복잡도는 현재 공간에서 recursion이 일어나지 않으므로 그대로 1

---

3. binary heap time complexity

👨‍🏫 위 여러 implementation 연산 time complexity를 정리해보면 아래와 같다.

operation	시간 복잡도
find max(root node 접근)	O(1)
heapify() (creating a heap)	O(n)
heapsort()	O(nlogn)
insertion	O(logn)
deletion / extracting max	O(logn)
increasing value in a heap	O(logn)

---

4. binary heap code using heapq in python

👨‍🏫 python에서 heapq라는 library를 지원해주어 heap 여러 implementation을 쉽게 구현할 수 있다.

 

👨‍🏫 heapq docu

heapq — Heap queue algorithm

 

👨‍🏫 python의 heapq는 default로 min-heap을 구현한다.

Q. heapsort using min-heap

import sys
import heapq
input=sys.stdin.readline
def heapsort(iterable):
    h=[]
    res=[]

    #모든 원소를 차례대로 heap에 삽입
    for value in iterable:
        heapq.heappush(h,value)
    
    #heap에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        res.append(heapq.heappop(h))
    return res

n=int(input())
arr=[]

for i in range(n):
    arr.append(int(input()))

res=heapsort(arr)

for i in range(n):
    print(res[i])

 

1) heapq의 heappush에 의해 min-heap 완성

2) min-heap이므로 heapq의 heappop에 의해 가장 마지막 node가 root node에 오면서 root node인 최솟값이 출력

3) 위 2)의 과정을 계속 반복하면서 출력되는 값을 나열하면 오름차순 정렬!

 

→ 수를 차례대로 집어넣으면, 오름차순 정렬대로 출력되어 나온다.

 

※ python의 경우 heapq는 min-heap 최소 힙을 구현해주는 library다. 따라서 오름차순으로 정렬된다 ※

Q. heapsort using max-heap

※ max-heap은 python의 경우 위 min-heap 구현 코드에 heappush 사용시 value에 음수를 붙여 heap에 집어넣고, 정렬한 뒤, heappop 사용할 때 다시 음수를 붙이면 된다.

import sys
import heapq
input=sys.stdin.readline
def heapsort(iterable):
    h=[]
    res=[]

    #모든 원소를 차례대로 heap에 삽입
    for value in iterable:
        heapq.heappush(h,-value)
    
    #heap에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        res.append(-heapq.heappop(h))
    return res

n=int(input())
arr=[]

for i in range(n):
    arr.append(int(input()))

res=heapsort(arr)

for i in range(n):
    print(res[i])

Q. building a heap - heapify()

 

→ min-heap(완전 이진 트리)을 실제로 만드는 heapify()는 O(n)의 시간 복잡도. 

import heapq

nums = [9,7,5,3,1]
heapq.heapify(nums)
print(nums) #[1,3,5,9,7]

Q. deletion using heappop() - find the nth smallest

 

① 위 만들어진 heap [1,3,5,9,7]에서

 

② 예를 들어 세 번째 작은 원소를 찾고 싶다면 총 두 번의 heappop() 수행한 뒤 O(1)이 걸리는 nums[0] 연산 수행

heapq.heappop(nums)
print(nums) #[3,7,5,9]

heapq.heappop(nums)
print(nums) #[5,7,9]

print(nums[0]) #5 
#heap의 node 출력

 

→ 세 번째 작은 원소 5 출력!

---

* heap youtube https://youtu.be/TK48r1Dlo4k

* binary heap wiki https://en.wikipedia.org/wiki/Binary_heap

* 썸네일 출처 https://www.digitalocean.com/community/tutorials/max-heap-java