Heap

# Heap

힙은 완전이진트리의 속성을 가지고 있습니다. 힙은 최대힙(Max Heap)과 최소힙(Min Heap)으로 구분할 수 있습니다.

최소힙(Min Heap)은 부모노드가 항상 자식 노드보다 작거나 같은 값을 가지고 있기 때문에 루트노드는 항상 트리의 최솟값을 갖고있게 되며, 반대로 최대힙(Max Heap)은 부모노드가 항상 자식도느 보다 크거나 같은 값을 가지고 있기 때문에 루트노드에 항상 트리의 최댓값을 갖고 있게 됩니다.

"항상"이기 때문에 어떤 연산을 하더라도 이 특성은 유지되어야 합니다

힙은 BST와는 다르게 중복값을 허용하며, 좌우 노드간의 값의 제약이 없고 상하 관계에서만 값의 제약을 갖게 됩니다

힙은 자료구조에서 최대 혹은 최소를 기준으로 데이터를 찾는 연산을 빠르게 해야 하는 상황에서 사용할 수 있습니다. 최댓값 최소값은 항상 루트노드에 있기 때문에 시간복잡도는 O(1)을 가집니다.

힙은 완전 이진트리이기 때문에 빈값이 없는 일차원 배열로 표현이 가능합니다. 특정 위치에서 노드의 인덱스는 아래 표의 연산으로 찾을 수 있습니다( 참고 : https://sonzwon.tistory.com/44?category=953980 앞 포스팅과 인덱스 연산 방법이 다른데, 그 이유는 파이선에서 코드를 구현함에 있어 0번 인덱스를 비우고 구현하는게 용이하지 않기 때문입니다)

부모노드	( i  - 1 ) /  2
왼쪽 자식 노드	i * 2 + 1
오른쪽 자식 노드	i * 2 + 2

(파이썬 코드구현에 쓰이는 인덱스 연산 방법입니다)

 

# 코드 구현 (python)

힙의 대표적인 응용에는 우선순위 큐가 있습니다 일반적인 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO 데이터구조였지만, 우선 순위 큐는 데이터가 들어온 순서에 상관없이 특정 기준을 두고 우선 순위가 높은 데이터 순으로 처리합니다. 그래서 최소힙으로 구현할 수 있습니다. 

MinHeap 클래스를 생성해줍니다.

class MinHeap:
    def __init__(self, list):
        self.data = list

[ Insert ] 

힙에서 데이터 추가는 leaf위치에 먼저 삽입한다음 힙의 특성에 맞게 해당 값의 위치를 찾아가도록 구현합니다. 

1. 완전 이진 트리 형태를 유지해야하므로 우선 leaf노드에 삽입합니다

2. 일단 leaf노드에 최소힙의 조건을 만족하는지 확인합니다( 만족하면 추가 연산 필요없이 삽입하면 됩니다.)

3. 힙의 조건을 만족하지 않을경우 삽입된 노드와 부모노드의 값을 바꿉니다.(heapify)

조건을 만족할 때 까지 위의 2-3번 과정을 반복하게 됩니다.

def insert(self, value):
    self.data.append(value)
    self.insert_heapify(len(self.data) - 1)

self.data.append(value)     리스트의 마지막에 새로운 데이터를 삽입합니다
self.insert_heapify(len(self.data) - 1)   삽입한 데이터가 힙의 조건을 만족하는 지 확인합니다

어떤 연산을 하더라도 힙의 속성을 유지해야하기 때문에 heapify(재구조화)를 해주어야 합니다. 처음 heapify를 동작시키면, 삽입된 데이터(가장 마지막 인덱스에 위치)의 인덱스를 파라미터로 받아옵니다,

def insert_heapify(self, idx):
    parent = (idx - 1) // 2
    if parent >= 0:
        if self.data[idx] < self.data[parent]:
            self.data[idx] =  self.data[parent]
            self.data[parent] = self.data[idx]
            self.insert_heapify(parent)

parent = (idx - 1) // 2     부모노드와 비교해야하므로 부모노드의 인덱스를 계산해줍니다.

최소힙에서는 부모노드가 자식노드보다 값이 작아야 합니다.
if parent >= 0:
    if self.data[idx] < self.data[parent]:        그래서, 삽입된데이터가 부모노드보다 값이작으면
        self.data[idx] =  self.data[parent]
        self.data[parent] = self.data[idx]       부모노드와 자식노드를 swap해줍니다.
        self.insert_heapify(parent)     그렇게 바뀐 위치가 힙의 조건을 만족하는지 확인하고 만족하지 않으면 반복합니다

 

[ pop ] 

최소힙은 최솟값을 다루기 위한 자료구조이므로 삭제연산에서는 최솟값만 삭제하도록 구현하겠습니다. 최솟값은 항상 루트노드에 있습니다.

1. 완전이진트리가 유지되어야 하므로 완전이진트리의 가장 마지막에 위치한 노드를 루트로 가지고 오면서 마지막 노드는 삭제합니다.

2. 힙의 조건을 만족하는 지 확인하고 만족하지 않으면 자식노드와 위치를 바꿉니다(삽입은 부모노드와 위치바꿈)

삽입 삭제과정에서는 이진트리에 데이터가 N개 있을 때 1/2씩 데이터를 줄여나가면서 자신의 위치를 찾기 때문에 O(logN)의 시간복잡도를 가집니다.

def pop(self):
    top = self.data[0]
    self.data[0] = self.data[-1]
    self.data.pop()
    self.pop_heapify(0)
    return top

top = self.data[0]              pop이되는 데이터는 루트에 위치합니다.
self.data[0] = self.data[-1]    완전이진트리의 속성을 유지하기 위해서 현재 가장마지막노드의 값을 루트노드로 가져옵니다
self.data.pop()                 데이터를 삭제합니다
self.pop_heapify(0)          heapify를 통해 힙의 조건을 만족하는 지 확인합니다
return top

어떤 연산을 하더라도 힙의 속성을 유지해야하기 때문에 heapify(재구조화)를 해주어야 합니다. 처음 heapify를 동작시키면, 루트의 인덱스를 파라미터로 받아옵니다,

def pop_heapify(self, idx):
    if self.isLeaf(idx):
        return
    left = 2 * idx + 1
    right = 2 * idx + 2
    curr = idx

    if left < len(self.data) and self.data[left] < self.data[curr]:
        curr = left
    if right < len(self.data) and self.data[right] < self.data[curr]:
        curr = right
    if curr != idx:
        self.data[idx], self.data[curr] = self.data[curr], self.data[idx]
        self.pop_heapify(curr)

if self.isLeaf(idx):
        return                      만약 인덱스가 leaf에 위치한다면 heapify는 동작하지않고 종료됩니다

부모노드가 더 작아야하는데 왼쪽자식노드와 오른쪽 자식노드와 비교해서 더 작은 값을 가져옵니다

    left = 2 * idx + 1          왼쪽자식노드의 인덱스 
    right = 2 * idx + 2        오른쪽자식노드의 인덱스
    curr = idx                    현재 위치의 인덱스(처음 동작시에는 루트노드)

    if left < len(self.data) and self.data[left] < self.data[curr]:     
        curr = left                  왼쪽 자식노드가 더 작으면 현재위치의 인덱스와 바꿔줍니다
    if right < len(self.data) and self.data[right] < self.data[curr]:   
        curr = right          오른쪽자식노드가 더 작으면 현재위치의 인덱스와 바꿔줍니다
    if curr != idx:                        작은 노드를 찾았으면
        self.data[idx], self.data[curr] = self.data[curr], self.data[idx]       두 값을 swap해줍니다
        self.pop_heapify(curr)      두 값을 바꾸고 힙의 조건을 만족하는지 확인하면서 반복합니다

 

# 전체 코드

MaxHeap은 MinHeap에서 부등호만 조금 바꿔주면 구현하실 수 있습니다

깃허브에서 MaxHeap과 다른 기능의 연산들, 테스트 코드를 포함한 전체 코드를 보실 수 있습니다.

GitHub - sonzwon/TIL: Today I Learned