[Data Structure] NonLinear - (2) Heap

---

---

 힙(Heap)

 힙 자료구조는 일종의 트리다. 힙은 형태 속성과 힙 속성을 만족해야 하는데, 즉 힙은 완전이진트리 구조여야 하며 힙 속성을 가져야 한다.

 

 완전이진트리는 이전 글에서 작성한 것처럼 마지막 레벨을 제외한 모든 노드가 다 채워져 있는 이진 트리이며, 마지막 레벨은 왼쪽에서 오른쪽으로 채워져 있는 트리이다. 힙 속성은 각 노드의 데이터들은 각각의 자식 노드의 데이터보다 크거나 같은 속성을 말한다.

 

힙 속성

 

---

힙 구현하기

 힙 자료구조 또한 완전이진트리 형태를 가지고 있으므로 동적 배열로 나타낼 수 있다. 즉, 파이썬에서는 리스트로 힙 자료구조를 표현할 수 있다.

 

 아래는 최대힙을 구현한 코드이다. 간단하게 heapify, heappop, heappush함수를 구현했다.

 

def _swap(arr, index_1, index_2):
    arr[index_1], arr[index_2] = arr[index_2], arr[index_1]


def heapify(arr):
    tree_size = len(arr)

    for i in reversed(range(tree_size//2)):
        _siftup(arr, i)


def _bubbleup(arr, index):
    while index > 0:
        parent_index = (index - 1) // 2
        if arr[index] > arr[parent_index]:
            _swap(arr, index, parent_index)
            index = parent_index
        else:
            break


def _siftup(arr, index):
    endposition = len(arr)

    left_child_index = 2 * index + 1
    right_child_index = 2 * index + 2

    largest = index

    if 0 < left_child_index < endposition and arr[largest] < arr[left_child_index]:
        largest = left_child_index

    if 0 < right_child_index < endposition and arr[largest] < arr[right_child_index]:
        largest = right_child_index

    if largest != index:
        _swap(arr, largest, index)
        _siftup(arr, largest)


def _siftdown(arr, index):
    endposition = len(arr)

    while True:
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2
        largest = index

        if left_child_index < endposition and arr[left_child_index] > arr[largest]:
            largest = left_child_index

        if right_child_index < endposition and arr[right_child_index] > arr[largest]:
            largest = right_child_index

        if largest == index:
            break

        _swap(arr, largest, index)
        index = largest


def heappush(arr, data):
    arr.append(data)
    _bubbleup(arr, len(arr) - 1)


def heappop(arr):
    if len(arr) == 0:
        return None

    root = arr[0]
    arr[0] = arr[-1]
    arr.pop()

    if len(arr) > 0:
        _siftdown(arr, 0)

    return root


a = [9, 2, 3, 4, 5, 10, 100]
heapify(a)
print(a)
heappush(a, 7)
print(a)
print(heappop(a))
print(a)
print(heappop(a))
print(a)
print(heappop(a))
print(a)
print(heappop(a))
print(a)

[100, 5, 10, 4, 2, 9, 3]
[100, 7, 10, 5, 2, 9, 3, 4]
100
[10, 7, 9, 5, 2, 4, 3]
10
[9, 7, 4, 5, 2, 3]
9
[7, 5, 4, 3, 2]
7
[5, 3, 4, 2]