JUNGLE 240326 (W01)

26 Mar 2024 in Study #Jungle

KRAFTON JUNGLE Week 01 (내 생일!!!🤍)

• 1. Keywords
  • 우선순위 큐 (Priority Queue)

1. Keywords

우선순위 큐 (Priority Queue)

• 큐의 각 요소에 우선 순위가 지정된 자료 구조
• 일반적으로 가장 높은 우선 순위를 가진 요소가 먼저 처리되는 자료 구조
• 힙(heap) 자료 구조를 사용하여 구현할 수 있음

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2   # 부모 노드의 인덱스

    def left_child(self, i):
        return 2 * i + 1      # 왼쪽 자식 노드의 인덱스

    def right_child(self, i):
        return 2 * i + 2      # 오른쪽 자식 노드의 인덱스

    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

• __init__(): 우선순위 큐 객체를 초기화
• parent(): 주어진 인덱스 i의 부모 노드의 인덱스를 반환
• left_child(), right_child(): 주어진 인덱스 i의 왼쪽, 오른쪽 자식 노드의 인덱스를 반환
• swap(): 주어진 인덱스 i, j의 값을 서로 교환

    def heapify_up(self, i):
        while i > 0 and self.heap[self.parent(i)][0] > self.heap[i][0]:
            self.swap(i, self.parent(i))
            i = self.parent(i)

    def heapify_down(self, i):
        min_index = i
        left = self.left_child(i)
        right = self.right_child(i)

        if left < len(self.heap) and self.heap[left][0] < self.heap[min_index][0]:
            min_index = left

        if right < len(self.heap) and self.heap[right][0] < self.heap[min_index][0]:
            min_index = right

        if i != min_index:
            self.swap(i, min_index)
            self.heapify_down(min_index)

• heapify_up(): 주어진 인덱스 i를 기준으로 부모 노드와 비교하여 힙 속성을 만족하도록 위로 올려가며 조정 (삽입 연산 시 사용)
• heapify_down(): 주어진 인덱스 i를 기준으로 자식 노드와 비교하여 힙 속성을 만족하도록 아래로 내려가며 조정 (삭제 연산 시 사용)

    def insert(self, priority, value):
        self.heap.append((priority, value))
        self.heapify_up(len(self.heap) - 1)

    def delete_min(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        min_value = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.heapify_down(0)
        return min_value

• insert(): 주어진 우선순위 priority와 값 value를 가진 요소를 우선순위 큐에 삽입
  • 힙에 새로운 요소가 들어 오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입
  • 삽입 후에 heapify_up을 호출해 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 유지
• delete_min(): 우선순위가 가장 높은 요소를 제거하고 반환
  • 최대 힙에서의 삭제는 가장 큰 키값을 가진 노드를 삭제하는 것 (루트 노드 삭제)
  • 마지막 노드를 루트 노드로 이동시킨 후 루트에서부터 단말 노드까지의 경로에 있는 노드들을 교환
  • 즉, heapify_down을 호출해 힙의 성질을 유지