자료구조와 알고리즘 - 힙(Heap)

 

---

 

 

힙(Heap)은 완전이진트리(자식노드의 개수가 최대 2개이며 왼쪽부터 오른쪽으로 채워나감)를 베이스로 구현된것으로,

부모노드의 값은 항상 자식 노드의 값보다 크거나 작다. 이때 형제노드간의 대소관계는 없다. 오직 부모, 자식노드 사이에만 대소 관계가 있다.

 

-최대 힙: 부모노드 >= 자식노드인 경우를 말한다.

 

 

 

 

-최소 힙: 부모노드 <= 자식노드 인 경우를 말한다.

 

 

 

 

 

 

 

-최대 힙의 삽입

 

 

-최대 힙의 삭제

 

 

-힙을 배열로 표현하는 방법

완전이진트리의 특성을 이용하여 힙을 배열로 만들 수 있다.

아래의 그림은 위의 이진트리를 배열로 표현한 것이고 다음과 같은 규칙이 있다. 

 

 

 

계산의 편의를 위해서 인덱스 0번자리는 비워둔다.(다른 글 참고하다보면 인덱스0부터 시작하는데도 있음)

 

노드들을 배열에 넣는 순서는 레벨을 아래로 내려가면서 왼쪽부터 채워나간다.

 

해당 배열의 인덱스 번호 i를 부모노드라고 한다면 2i번째 위치는 왼쪽자식노드, 2i+1번째 위치는 오른쪽자식노드가 된다.

 

힙을 배열로 표현하는 것이 트리로 표현하는 것보다 좋다.

 

이유는 데이터를 삽입, 조회, 삭제하는데 배열은 위처럼 규칙을 알고 있기 때문에 트리구조보다 빠르다.(트리는 순회를 해야한다.) 

그리고 트리로 직접 구현을 하면 각종 조건들을 걸게 되는데(왼쪽자식이 비었는지, 왼쪽으로 갈지, 오른쪽으로 갈지 등등) 이는 코드가 복잡해지고 이해하기가 어려워 질 수 있다. 

 

 

class maxheap():
    def __init__(self, data):
        self.array = [None]
        self.array.append(data)

    def add_(self, data):
        self.array.append(data)
        child_idx = len(self.array)-1
        parent_idx = child_idx//2
        while self.array[parent_idx] < self.array[child_idx]:   #자식노드와 부모노드 비교하는 과정
            self.array[parent_idx], self.array[child_idx] = self.array[child_idx], self.array[parent_idx]
            child_idx = parent_idx
            parent_idx = child_idx//2
            if parent_idx == 0:   #루트노드에 도달하게 된다면 중단
                break

    def pop_(self):
        if len(self.array)>1:
            left_pop_data = self.array[1]
            self.array[1] = self.array[-1]   #루트노드 빼고 가장 마지막 노드를 루트노드에 대입   
            
            self.array.pop()
            length = len(self.array)-1

            parent_idx = 1
            child_left = parent_idx*2
            child_right = child_left+1

            while child_left <= length or child_right <= length:
                stand = self.array[parent_idx]
                direction = ""
                if stand < self.array[child_left]:
                    stand = self.array[child_left]
                    direction = "L"
                #3개 남았을때 오른쪽부터 나가짐 그래서 오른쪽에 이 항목 추가(추가안하면 index에러남)    
                if child_right <= length and stand < self.array[child_right]:  
                    stand = self.array[child_right]
                    direction = "R"

                if direction == "L":
                    self.array[parent_idx], self.array[child_left] = self.array[child_left], self.array[parent_idx]     
                    parent_idx = child_left
                    child_left = parent_idx*2
                    child_right = child_left+1
                elif direction == "R":
                    self.array[parent_idx], self.array[child_right] = self.array[child_right], self.array[parent_idx]
                    parent_idx = child_right
                    child_left = parent_idx*2
                    child_right = child_left+1
                else:
                    break
            return left_pop_data       
        else:
            print("비었습니다.")

 

 

heap = maxheap(29)
heap.add_(20)
heap.add_(10)
heap.add_(15)
heap.add_(1)
heap.add_(6)
heap.add_(8)
heap.array

 

                                                           

위의 트리를 배열로 표현

 

 

 

##데이터 삽입
heap.add_(21)
heap.array

삽입의 최종 결과를 배열로 표현

 

 

 

#데이터 삭제
heap.pop_()
heap.array

삭제의 최종 결과를 배열로 표현

 

-힙은 우선순위 큐(우선순위 높은 데이터가 먼저 나가는 자료구조)를 구현하는데 쓰인다. 그리고 이를 이용한 힙정렬을 구현할 수 있다.