[자료구조] 힙 (Heap) 구조 -Data Structure with 파이썬

힙 (Heap) 

• 트리를 기반으로 해 어떠한 목적에 따라 변환시킨 자료구조이다.
• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
  • 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

 

사용하는 이유

• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림
• 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, O(logn) 이 걸림
• 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨

 

 

힙의 완전 이진트이와 이진탐색트리의 차이점

구조의 조건

1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
   • 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음
2. 완전 이진 트리 형태를 가짐

즉 최대 힙(Heap)은 맨위의 값이 최대값을 가지는 것이고 최소 힙(Heap)은 맨 위의 값이 최소 값을 가지게 되는 것이다.

 

데이터 삽입시 조건

맨 왼쪽 노드 부터 채워나가는데 level 1이 루트노드라 하면 level별로 왼쪽 부터 채워나간다는 것이다.

이때 맨 왼쪽 노드에 삽입부터하고 삽입한 데이터의 부모노드와 방금 삽입한 데이터간 크기 비교를 통해 swap 후 저장을 해야한다.

 

데이터 삭제시

• Max Heap의 경우 보통 최상단 노드 (root 노드)를 삭제하는 것이 일반적
• Min Heap의 경우 보통 최상단 노드 (root 노드)를 삭제하는 것이 일반적

• 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지막에 추가한 노드) 를 root 노드로 이동
• root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복함 (swap)

 

우선순위 큐의 구현에 어울리는 것은 힙이며 힙은 연결리스트와 배열을 이용하는 방법이 있는데 배열기반으로 구현해야한다. 

왜냐하면 연결리스트를 기반으로 힙을 구현시 새로운 노드를 힙의 마지막 위치에 추가하는 것이 쉽지 않다는 사소한 이유 때문이다.

 

힙 구현

• 배열 자료구조를 활용
• 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀더 수월
• reheapup
  • 맨 밑에서부터 비교해서 위로 올라간다.
  • 이렇기 때문에 레벨이 가장 큰 즉 마지막으로 삽입한 데이터에 대해 진행해야한다.
• reheapdown
  • 맨 위에서인 루트노드부터 비교해서 밑으로 내려간다.
  • 이렇기 때문에 루트노드에서 부터 시작한다.
    • 이런 성질로 delete를 할때에는 위에서 부터 삭제를 하니 이것을 사용한다. 

 

맨처음 내가 생각했던것 (max_heap기준)

class Heap:
    def __init__(self,data):
        self.array=list()
        self.array.append(None)
        self.array.append(data)

    def insert(self,data):
        if len(self.array)==0:
            self.array.append(None)
            self.array.append(data)
        self.array.append(data)

        self.max_heap()
        return True

    def max_heap(self):
        for i in range(len(self.array)-1,1,-1):
            if self.array[i]>self.array[i//2]:
                self.array[i],self.array[i//2]=self.array[i//2],self.array[i]

    def min_heap(self):
        for i in range(len(self.array)-1,1,-1):
            if self.array[i]<self.array[i//2]:
                self.array[i],self.array[i//2]=self.array[i//2],self.array[i]

    def print_all(self):
        print(self.array)

    def delete(self,data):
        pass

그런데 위의 것에서 reheapup에 해당하는 max_heap, min_heap이 O(n)의 성질을 가지기 때문에 heap을 구현했다고 할 수 없었다.

 

다시 구현 (max_heap기준)

 

reheapdown구현

case1: 왼쪽 자식 노드도 없을 때
case2: 오른쪽 자식 노드만 없을 때
case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때

 

delete 구현

특징 - 위에서 reheapdown에서의 False에 해당하는 것은 while문이 끝나게 하는 것으로 reheapdown에서 구현했으니 delete에서는 구현할 필요가 없다.

case2: 오른쪽 자식 노드만 없을 때
case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때

 

class Heap:
    def __init__(self,data):
        self.array=list()
        self.array.append(None)
        self.array.append(data)

    def insert(self,data):
        if len(self.array)==1:
            self.array.append(None)
            self.array.append(data)
            return True

        self.array.append(data)

        inserted_idx = len(self.array)-1
        while self.re_heap_up(inserted_idx):
            parent_idx=inserted_idx//2
            self.array[inserted_idx],self.array[parent_idx]=self.array[parent_idx],self.array[inserted_idx]
            inserted_idx=parent_idx
        return True

    def re_heap_up(self,inserted_idx):
        if inserted_idx <= 1:
            return False
        parent_idx=inserted_idx//2
        if self.array[inserted_idx] > self.array[parent_idx]:
            return True
        else:
            return False

    def re_heap_down(self,pop_idx):
        right_child_pop_idx=pop_idx*2+1
        left_child_pop_idx = pop_idx * 2

        if left_child_pop_idx>=len(self.array):
            return False
        elif right_child_pop_idx>=len(self.array):
            if self.array[pop_idx]<self.array[left_child_pop_idx]:
                return True
            else:
                return False
        else:
            if self.array[left_child_pop_idx] <self.array[right_child_pop_idx]:
                if self.array[pop_idx]<self.array[right_child_pop_idx]:
                    return True
                else:
                    return False
            else:
                if self.array[pop_idx] < self.array[left_child_pop_idx]:
                    return True
                else:
                    return False

    def print_all(self):
        print(self.array)

    def delete(self):
        if len(self.array)<=1:
            return None
        returned_data=self.array[1]
        self.array[1]=self.array[-1]
        del self.array[-1]
        pop_idx=1
        while self.re_heap_down(pop_idx):
            right_child_pop_idx = pop_idx * 2 + 1
            left_child_pop_idx = pop_idx * 2
            if right_child_pop_idx >= len(self.array):
                if self.array[pop_idx] < self.array[left_child_pop_idx]:
                    self.array[pop_idx],self.array[left_child_pop_idx]=self.array[left_child_pop_idx],self.array[pop_idx]
                    pop_idx=left_child_pop_idx
            else:
                if self.array[left_child_pop_idx] > self.array[right_child_pop_idx]:
                    if self.array[pop_idx] < self.array[left_child_pop_idx]:
                        self.array[pop_idx], self.array[left_child_pop_idx] = self.array[left_child_pop_idx],self.array[pop_idx]
                        pop_idx = left_child_pop_idx
                else:
                    if self.array[pop_idx] < self.array[right_child_pop_idx]:
                        self.array[pop_idx], self.array[right_child_pop_idx] = self.array[right_child_pop_idx],self.array[pop_idx]
                        pop_idx = right_child_pop_idx
        return returned_data

이런식으로 하게 된다면 reheapup이나 reheapdown에 해당하는 것으로 인해 2개의 노드 중 하나의 노드로 가게 된다. 이렇기 때문에 O(logn)을 가지게 된다.

 

 

힙 (Heap) 시간 복잡도

• depth (트리의 높이) 를 h라고 표기한다면,
• n개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제시, 최악의 경우 root 노드에서 leaf 노드까지 비교해야 하므로 h=log2n 에 가까우므로, 시간 복잡도는 O(logn)
  • 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함