[Data Structure] 힙 (Heap)의 구현 - 힙과 배열

힙과 배열

• 일반적으로 힙 구현 시, 배열 자료구조 활용
• 배열은 인덱스 0 부터 시작하지만, 힙 구현의 편의를 위해 root 노드 인덱스 번호를 1로 지정
  • 부모 노드 인덱스(parent node's index) = 자식 노드 인덱스(child node's index) //2
  • 왼쪽 자식 노드 인덱스(left child node's index) = 부모 노드 인덱스(parent node's index) * 2
  • 오른쪽 자신 노드 인덱스(right child node's index) = 부모 노드 인덱스(parent node's index) * 2 + 1

Heap 과 인덱스 번호

힙과 데이터 삽입(Max Heap)

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


heap = Heap(1)
heap.heap_array  #[None, 1]

• insert()

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)
    return True

• insert() 변형 : 삽입한 노드가 부모 노드값보다 클 경우, 부모 노드와 삽입노드 위치 변경

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

 

힙의 데이터 삭제(Max Heap)

• 보통 삭제는 최상단 노드(root node)를 삭제하는 것이 일반적
• (cf. 힙의 용도는 최대값 또는 최소값을 root node에 놓아서, 빠르게 꺼내쓰도록 하는 것)

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

    def pop(self):
        if len(self.heap_array) <= 1:
            return None

        returned_data = self.heap_array[1]
        return returned_data

 

힙(Heap) 시간 복잡도

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