1. 힙

• 내부 표현 : 동적배열, 완전 이진 트리
• 최대 힙과 최소 힙으로 나눌 수 있음

1) 최대 힙(max heap)

• 최대 트리이면서 완전 이진트리
• 최대트리 : 어떤 노드의 키가 자식의 키보다 작지 않은 트리
  parent.key >= child.key
• 완전 이진 트리 : 트리 높이가 h일 때 h-1레벨까지는 2^h-1 - 1의 노드를 가짐
• 인덱스를 0이 아닌 1부터 가짐
  ex ) 14, 11, 9, 2, 6, 8 순으로 인덱스 1씩 증가
• 부모 인덱스 : 자식 인덱스 / 2
  ex) 키 9를 가진 인덱스 / 2 = 1로 부모인덱스는 키 14를 가진 노드임
• 자식 인덱스 : 왼쪽 자식 노드의 경우 부모 인덱스 2, 오른쪽 자식 노드의 경우, 부모 인덱스 2 + 1

  • index(parent) = index(child) // 2
  • index(left_child) = index(parent) * 2
  • index(right_child) = index(parent) * 2 + 1

• heapsize : 힙에 저장된 키의 개수 = 힙의 마지막 키의 인덱스

1-1) ADT

• Object : 키 속성을 지닌 요소 집합
• Operation
  • h.is_empty() : Boolean, 힙이 비어있으면 True, 아니면 False
  • h.is_full() : Boolean, 힙이 가득차있으면 True, 아니면 False
  • h.push(element) : 힙에 요소 삽입
  • h.pop() : element, 힙에서 최대 원소를 삭제하고 그 원소 반환

1-2) 구현

class Element:
    def __init__(self, key):
        self.key = key

class MaxHeap:
    MAX_ELEMENT = 100

    def __init__(self):
        self.arr = [None for i in range(self.MAX_ELEMENT+1)]
        self.heapsize = 0

    def is_empty(self):
        if self.heapsize == 0:
            return True
        return False
    
    def is_full(self):
        if self.heapsize >= self.MAX_ELEMENT:
            return True
        return False
        
	def parent(self, idx):
        return idx >> 1
    
    def left(self, idx):
        return idx << 1

    def right(self, idx):
        return (idx<<1) + 1

• Element 클래스 : 우선적으로는 키값만 가지고 있음.
• parent 함수 : 인덱스를 매개변수로 받아 그 노드의 부모 인덱스 반환
  • idx >> 1 == idx // 2
• left 함수 : 왼쪽 자식 반환
  • idx << 1 == idx * 2

    ex) 14, 2, 9 에 11 삽입
    1) 완전 이진 트리 속성을 만족하기 위해 2의 왼쪽 서브트리로 11이 삽입됨 -> 최대 힙 특성 깨짐
    2) 최대 힙 속성 만족을 위해 2와 11의 위치를 바꿈

def push(self, item):
        if self.is_full():
            raise IndexError("the heap is full")
        
        self.heapsize += 1
        cur_idx = self.heapsize

        while cur_idx != 1 and item.key > self.arr[self.parent(cur_idx)].key:
            self.arr[cur_idx] = self.arr[self.parent(cur_idx)]
            cur_idx = self.parent(cur_idx)
        self.arr[cur_idx] = item

• self.heapsize += 1; cur_idx = self.heapsize; : 완전 이진 트리를 유지하기 위해 마지막 원소의 다음 인덱스에 삽입
• while cur_idx != 1 and item.key > self.arr[self.parent(cur_idx)].key: : cur_idx가 루트가 아니고 item의 키가 cur_idx 부모 키보다 큰 경우 실행

pop 연산 : 최대값을 삭제함 = 즉, 루트 삭제
1) pop() 을 통해 최대값인 루트 노드 삭제 -> 최대 힙 특성 깨짐
2) heap의 마지막 요소를 루트 노드로 대체함 = temp 값
3) temp값의 자식 노드 중 키가 더 큰 값을 선택하여 바꿔주면 됨

def pop(self):
        if self.is_empty():
            return None
        
        rem_elem = self.arr[1]

        temp = self.arr[self.heapsize]
        self.heapsize -= 1

        cur_idx = 1
        child = self.left(cur_idx)

        while child <= self.heapsize:
            if child < self.heapsize and self.arr[self.left(cur_idx)].key < self.arr[self.right(cur_idx)].key:
                child = self.right(cur_idx)
            if temp.key >= self.arr[child].key:
                break
            self.arr[cur_idx] = self.arr[child]
            cur_idx = child
            child = self.left(cur_idx)
            
        self.arr[cur_idx] = temp
        return rem_elem

• temp = self.arr[self.heapsize]; self.heapsize -= 1 : 맨 마지막에 위치한 원소를 받아오면서 heapsize를 하나 줄임
• cur_idx = 1 : 루트에서 시작
• child = self.left(cur_idx) : 루트 왼쪽 자식
• while child <= self.heapsize: : child > self.heapsize면 arr[cur_idx]는 리프노드임.
• if child < self.heapsize and self.arr[self.left(cur_idx)].key < self.arr[self.right(cur_idx)].key : child = self.right(cur_idx) : 오른쪽 자식이 있고, 오른쪽 자식의 키가 왼쪽 자식의 키보다 크면 child를 오른쪽 자식으로 이동
• if temp.key >= self.arr[child].key : break : 최대 힙 특성 만족 시 break
• self.arr[cur_idx] = self.arr[child]; cur_idx = child : key가 큰 원소를 부모로 이동시킴.
• 루트에 있는 키를 반환하고 빈 루트에 트리의 맨 마지막 원소를 임시로 올림. 자식 노드의 키값과 비교하며 자신의 위치를 찾아감

def print_heap(h):
    for i in range(1, h.heapsize+1):
        print("{}".format(h.arr[i].key), end=" ")
    print()

if __name__ == "__main__":
    h = MaxHeap()

    h.push(Element(2))
    h.push(Element(14))
    h.push(Element(9))
    h.push(Element(11))
    h.push(Element(6))
    h.push(Element(8))

    print_heap(h)

    while not h.is_empty():
        rem = h.pop()
        print(f"poped item is {rem.key}")
        print_heap(h)

2. 우선순위 큐

• 키를 가진 원소 집합을 위한 자료 구조
• 힙으로 구현

2-1) ADT

• Object : 키를 가진 원소 집합
• Operation
  • is_empty() : Boolean, 큐가 비어있음 True, 아니면 False
  • push(item) : 큐에 Item 삽입
  • pop() : element, 큐에서 키가 가장 작은 값 삭제하면서 반환
  • min() : element, 큐에서 키가 가장 작은 값 반환
  • decrease_key(item, new_key) : 큐에 있는 아이템의 키를 값이 줄어든 new_key 값으로 수정
• decrease_key() : 프림 알고리즘, 다익스트라 알고리즘에서 필요한 연산으로 현재 단계에서는 직접 구현하지 않음
• heapq 모듈 사용 : 우선순위 큐 구현을 위한 힙의 구현 제공(최소 힙만 제공), 인덱스도 0부터 시작함(루트 0부터 시작함)

2-2) 구현

from heapq import heappop, heappush

class Element:
    def __init__(self, key, string):
        self.key= key
        self.data = string

class MinPriorityQueue:
    def __init__(self):
        self.heap = []
    
    def is_empty(self):
        if not self.heap:
            return True
        return False
    
    def push(self, item):
        heappush(self.heap, (item.key, item.data))
    
    def pop(self):
        return heappop(self.heap)

    def min(self):
        return self.heap[0]

if __name__ == "__main__":
    pq = MinPriorityQueue()

    pq.push(Element(2, "kim"))
    pq.push(Element(14, "park"))
    pq.push(Element(9, "choi"))
    pq.push(Element(11, "lee"))
    pq.push(Element(6, "yang"))
    pq.push(Element(8, "jang"))

    while not pq.is_empty():
        elem = pq.pop()
        print(f"key[{elem[0]}] : data[{elem[1]}]")

• heappush(self.heap, (item.key, item.data)) : key, data를 튜플로 묶어서 전달