Heap이란:

1) 힙은 Complete Binary Tree이다.

2) 모든 노드에 저장된 값(우선순위)들은 자식 노들의 것보다 (우선순위가 크거나 같다.)

• 직접 연결된 자식-부모 노드 간의 크기만 비교하면 된다.

• 힙으로 우선순위 큐를 구현할 떄에는 노드에 저장된 값을 우선순위로 본다.

따라서 힙은 루트 노드에 우선순위가 높은 데이터를 위치시키는 자료구조이다.

그러므로 우선순위 큐를 구현하는데 알맞은 자료구조이다.

최대 힙(max heap)은 완전이진 트리이면서, 루트 노드로 올라갈수록 저장된 값이 커지는 구조이다.

그리고 우선순위는 값이 큰 순서대로 매기게 된다.

힙이 가지는 장점은?

삽입/삭제 연산이 BST보다 빠르다.
트리를 사용하기 떄문에 시간 복잡도 O(lg(n))으로 돌일하지만 힙은 무조건 완전 이진트리여야 하므로 모든 삭제/삽입 연산이 끝에서 발생한다.

최소 힙(min heap)은 완전이진 트리이면서, 루트 노드로 올라갈수록 저장된 값이 작아지는 구조이다.

그리고 우선순위는 값이 작은 순서대로 매기게 된다.

결국 최대 힙이던 최소 힙이던 루트 노드에는 우선순위가 높은 것이 자리잡게 된다.

Heap의 데이터 저장:

1) 최소 힙에 저장할때

위와 같은 최소 힙에 어떤 노드 하나가 추가로 들어올때 노드에 저장된 값들을 우선순위로 생각하며, 숫자가 작은 순서대로 우선순위가 높은것이다.

제일 먼저, 들어올 새 노드를 우선 순위가 가장 낮다라고 가정하고, 맨 끝 위치에 저장한다. 맨 끝 위치에 저장한다는 것도 완전 이진트리를 만족하는 틀 안에서 이루어져야 하므로, 위 그림에서는 새로 들어올 노드가 노드 7의 left child로 들어가야 한다.

그리고 부모 노드와 우선 순위를 비교해서 위치가 바뀌어야 하면 바꾼다.
위치가 맞을때까지 계속 반복한다.

새로 들어올 노드의 값이 3이라고 가정

대략적인 과정은 이렇다. 최대힙은 반대로 부모와 비교해 자식이 크면 서로 자리바꿈하면 된다.

우선순위 큐를 나타내기 적합한 완전 이진트리인 '힙'을 무엇을 기반으로 구현하는게 용이할까요?

여기에서는 배열 구현이 좋다.

Heap의 데이터 삭제:

1) 최소 힙에서 삭제할때

힙 우선순위 큐의 구현을 위해 사용하기로 했다.

우선순위 큐에서의 데이터 삭제는 곧 , 가장 우선순위가 높은 데이터를 빼낸다는 의미이다.

그렇다면 힙에서 가장 우선순위가 높은 데이터는 루트노드인데, 이 루트 노드를 삭제하면서 힙의 구조를 그대로 유지하는 것이 삭제의 관건이다.

계속 진행해 나가면서 최소 힙의 구조를 유지할때까지 반복한다.

Heap 코드:

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

    def move_up(self,inserted_idx):
            if inserted_idx<=1:
                return False
            parent_idx = inserted_idx // 2
            if self.heap_array[inserted_idx]>self.heap_array[parent_idx]:
                return True
            else:
                return False
        
    def insert(self,data):
            if len(self.heap_array)==0:
                self.heap_array.append(None)
                self.heap_array.append(data)
                return True
            self.heap_array.append(data)

            inserted_idx = len(self.heap_array)-1
            while self.move_up(inserted_idx) : # 부모노드와의 비교
                parent_idx = inserted_idx // 2
                self.heap_array[inserted_idx],self.heap_array[parent_idx] = self.heap_array[parent_idx],self.heap_array[inserted_idx]
                inserted_idx = parent_idx

            return True


    def move_down(self,popped_idx):
            left_child_popped_idx = popped_idx * 2
            right_child_popped_idx = popped_idx * 2+ 1
            # case1: 왼쪽 자식 노드도 없을때
            if left_child_popped_idx>=len(self.heap_array):
                return False
            # case2: 오른쪽 자식 노드만 없을때
            elif right_child_popped_idx >= len(self.heap_array):
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    return True
                else: 
                    return False
            # case3: 왼쪽,오른쪽 자식 모두 있을때
            else:
                # 왼쪽이 더 큰 경우
                if self.heap_array[left_child_popped_idx]> self.heap_array[right_child_popped_idx]:
                    if self.heap_array[popped_idx]<self.heap_array[left_child_popped_idx]:
                        return True
                    else:
                        return False
                else:
                    # 오른쪽이 더 큰 경우
                    if self.heap_array[popped_idx]<self.heap_array[right_child_popped_idx]:
                        return True
                    else:
                        return False

        
    def pop(self):
            # 원리 : 맥스힙의 pop은 root를 삭제하는것이다.
            # 구현 원리는 맨 최상단 root를 tatil 위치의 노드로 복사해놓고, 마지막 노드를 삭제한 후 정렬해주면된다.
            if len(self.heap_array)<=1: # pop 할것이 없는 루트 노드
                return None
        
            returned_data = self.heap_array[1]
            self.heap_array[1] = self.heap_array[-1]
            del self.heap_array[-1]
            popped_idx = 1

            while self.move_down(popped_idx):
                left_child_popped_idx = popped_idx*2
                right_child_popped_idx = popped_idx*2+1

                #case 1: 왼쪽 자식 노드도 없을때
                if left_child_popped_idx >= len(self.heap_array):
                    pass
                #case 2 : 오른쪽 자식 노드만 없을떄
                elif right_child_popped_idx>= len(self.heap_array):
                    if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                        self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx] , self.heap_array[popped_idx]
                        popped_idx = left_child_popped_idx
                #case 3: 왼쪽, 오른쪽 자식 모두 있을때
                else:
                    # 왼쪽이 더 큰 경우
                    
                    if self.heap_array[left_child_popped_idx]>self.heap_array[right_child_popped_idx]:
                        if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                            self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx] , self.heap_array[popped_idx]
                            popped_idx = left_child_popped_idx 
                    else:
                        if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                            self.heap_array[popped_idx], self.heap_array[right_child_popped_idx] = self.heap_array[right_child_popped_idx] , self.heap_array[popped_idx]
                            popped_idx = right_child_popped_idx 
                    
            return returned_data
                        

def main():
    heap = Heap(15)
    heap.insert(10)
    heap.insert(8)
    heap.insert(5)
    heap.insert(4)
    heap.insert(20)
    heap.heap_array
    heap.pop()
    print(heap.heap_array[1])




if __name__ == "__main__":
    main()

---

참고:

링크텍스트