[자료구조] 힙

힙

• 가장 큰, 작은 데이터를 빠르게 찾기 위해 고안된 완전이진트리
• 완전 이진트리 : 왼쪽부터 노드를 삽입하는 이진트리
• 힙을 사용하는 이유
  • 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림
  • 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, O(log n) 이 걸림 - n은 노드의 개수임
  • 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨
• 힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수 있음
• 힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조임
  1. 부모 노드는 자식노드보다 크거나(max), 작거나(min) 같다.
  • 루트 노드가 가장 큰(작은) 값이 됨
  2. 완전 이진 트리 형태를 가짐

힙과 이진 탐색 트리의 공통점과 차이점

• 공통점: 힙과 이진 탐색 트리는 모두 이진 트리임
• 차이점:
  • 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
  • 이진 탐색 트리는 왼쪽 자식->부모 노드-> 오른쪽 자식노드 순으로 값이 커짐
  • 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
    • 힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음
• 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨
  
  출처

파이썬으로 힙 구현해보기

• 힙은 왼쪽부터 삽입되기 때문에 배열의 인덱스번호로 생각하면 쉬움
• 0번 인덱스는 None으로
• 루트노드부터 순서대로 1,2,3으로 ..
• 부모노드 = 자식노드//2
• 왼쪽자식노드 = 부모노드 *2
• 오른쪽자식노드 = 부모노드 *2 +1

class Heap:
    def __init__(self,data):
        self.heap_array=list()
        self.heap_array.append(None)
        self.heap_array.append(data)
        
    def move_up(self,insert_idx):
        #삽입된 노드가 root노드 일 경우
        if insert_idx<=1:
            return False
        parent_idx=insert_idx//2
        #부모 노드 보다 삽입된 노드가 더 클 경우
        if self.heap_array[parent_idx]<self.heap_array[insert_idx]:
            return True
        else:
            return False
        
    def insert(self,data):
        #만약 빈 heap이라면
        if len(self.heap_array)==0:
            self.heap_array.appned(None)
            self.heap_array.append(data)
            return True
        #빈 heap이 아니라면, 마지막에 data를 넣어주고    
        self.heap_array.append(data)
        insert_idx = len(self.heap_array)-1
        #넣은 노드가 부모노드보다 크다면
        #부모노드랑 삽입된 노드랑 바꾼다
        while self.move_up(insert_idx):
            parent_idx = insert_idx//2
            self.heap_array[parent_idx],self.heap_array[insert_idx]=self.heap_array[insert_idx],self.heap_array[parent_idx]
            insert_idx=parent_idx
        return True
        
    def move_down(self,popped_idx):
            popped_idx_left_idx = popped_idx*2
            popped_idx_right_idx = popped_idx*2+1
            
            #왼쪽자식도 없을 경우
            if popped_idx_left_idx >= len(self.heap_array):
                return False
            # 왼쪽자식만 있을 경우
            elif popped_idx_right_idx >= len(self.heap_array):
                #자식>부모 
                if self.heap_array[popped_idx_left_idx]>self.heap_array[popped_idx]:
                    return True
                else:
                    return False
            # 자식 둘다 있는 경우
            else:
                #왼쪽자식>오른쪽자식
                if self.heap_array[popped_idx_left_idx]>self.heap_array[popped_idx_right_idx]:
                    #왼쪽자식>부모
                    if self.heap_array[popped_idx_left_idx]> self.heap_array[popped_idx]:
                        return True
                    #왼쪽자식<부모
                    else:
                        return False
                #왼쪽자식<오른쪽자식
                else:
                    #오른쪽자식>부모
                    if self.heap_array[popped_idx_right_idx]> self.heap_array[popped_idx]:
                        return True
                    #오른쪽자식<부모
                    else:
                        return False
        
    def pop(self):
            #빈 노드 일 경우
            if len(self.heap_array)<=1:
                return None
            #빈 노드가 아닌 경우
            #root 노드를 리턴하고, 마지막 노드를 최상단에 올린다
            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):
                popped_idx_left_idx = popped_idx*2
                popped_idx_right_idx = popped_idx*2+1
            
            # 왼쪽자식만 있을 경우
                if popped_idx_right_idx >= len(self.heap_array):
                    #자식>부모 
                    if self.heap_array[popped_idx_left_idx]>self.heap_array[popped_idx]:
                        self.heap_array[popped_idx_left_idx],self.heap_array[popped_idx]=self.heap_array[popped_idx],self.heap_array[popped_idx_left_idx]
                   
                # 자식 둘다 있는 경우
                else:
                    #왼쪽자식>오른쪽자식
                    if self.heap_array[popped_idx_left_idx]>self.heap_array[popped_idx_right_idx]:
                        #왼쪽자식>부모
                        if self.heap_array[popped_idx_left_idx]> self.heap_array[popped_idx]:
                            self.heap_array[popped_idx_left_idx],
                        self.heap_array[popped_idx]=self.heap_array[popped_idx], self.heap_array[popped_idx_left_idx]
                       
                    #왼쪽자식<오른쪽자식
                    else:
                        #오른쪽자식>부모
                        if self.heap_array[popped_idx_right_idx]>self.heap_array[popped_idx]:
                            self.heap_array[popped_idx_right_idx],self.heap_array[popped_idx]=self.heap_array[popped_idx],self.heap_array[popped_idx_right_idx]
            return returned_data                
                   
                        
heap= Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
heap.insert(20)
print(heap.pop())
print(heap.heap_array)