포인터 기반의 연결 방식(2) - 추상 데이터 타입(힙과 우선순위 큐)

책 <파이썬 자료구조와 알고리즘>을 기본으로 배운 자료구조 내용입니다

 

목차

• 추상 데이터 타입 - 힙(최대힙 구현), 우선순위 큐

 

<추상 데이터 타입 - 힙과 우선순위 큐>

힙

• 각 노드가 하위 노드보다 작은/큰 이진 트리.
• 리스트에서 가장 작은/큰 요소에 반복적으로 접근하는 프로그램에 적합함.
• 시간 복잡도 : 최소/최대 요소 처리는 O(1), CRUD는 O(log n)이다.

heapq 모듈 : 효율적으로 시퀀스를 힙으로 유지하면서 항목을 삽입,제거하는 함수 제공

heapq.heapify()	라스트를 힙으로 변환 (시간복잡도 : O(n))
heapq.heappush(heap, item)	힙에 원소 추가
heapq.heappop(heap)	힙에서 가장 작은 항목 제거, 반환
heapq..heappushpop(heap, item)	힙에 새 항목 추가 후 가장 작은 항목 제거, 반환
heapq.heapreplace(heap, item)	가장 작은 항목 제거, 반환 후 힙에 새 항목 추가
heapq.merge(*iterables)	여러 개의 정렬된 반복 가능한 객체를 병합하여 하나의 정렬된 결과의 이터레이터를 변환
heapq.nlargest/nsmallest(n, iterables[, key])	데이터에서 n개의 가장 큰 요소와 가장 작은 요소가 있는 리스트를 반환

heap의 종류 

• 최대 힙 : 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙, 값이 클 수록 우선 순위 높다.
  
• 최소 힙 : 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙, 값이 작을 수록 우선 순위 높다.
  
• 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다

index

• parent index = child index // 2
• left child index = parent index * 2
• right child index = paretn index * 2 + 1

 

최대 힙 구현

1. i = 배열의 길이//2
2. 자식이 있는 노드까지 i-1반복
3. 자식이 있는 노드에서 자식 노드의 값과 바교, 자식 노드의 값이 더 크면 교환
4. (3번에서 부모 노드 였던)교환된 자식 노드으로 넘어가 다시 자식 노드의 값과 비교, 자식 노드의 값이 더 크면 교환

insert() 구현

1. 맨 마지막 노드에 새로운 데이터 추가 (완전 이진트리 유지 - 최고 깊이에서 가장 오른쪽에 노드 추가)
2. 부모 노드와 비교, 부모보다 신규 노드가 크다면(우선 순위가 높다면) 교환
3. 반복하여 부모 노드와 비교
4. 루트 노드에 도달했거나 (부모가 없음) 부모 노드가 더 크거나 같다면 멈춘다.

delete() 구현

1. 루트 노드(최대힙에선 최댓값)를 반환
2. 맨 마지막 노드를 루트 노드로 이동 (A)
3. 두 자식 노드를 비교해 우선 순위가 높은 것을 선택 (최대 힙인 경우 큰 수) (B)
4. A 와 선택된 자식노드 (B) 를 비교하여 우선순위가 높은 것을 부모노드로 이동
5. 반복하여 자식 노드와 비교
6. 터미널 노드(자식이 없는 노드)에 도달했거나 자식노드가 더 작거나 같다면 멈춘다.

배열을 이용한 힙 구현

class Heap:
    # 개체들이 공유하는 메소드는 클래스 메소드로 만들어도 된다.
    def get_parent_idx(self, idx):
        return idx // 2

    def get_left_child_idx(self, idx):
        return idx * 2

    def get_right_child_idx(self, idx):
        return idx * 2 + 1

    # 중요함수- 보통은 유저 프로그래머가 직접 구현, 인터페이스만 제공
    # 우선순위에 따라 반환값이 달라진다.
    def get_prior(self, value1, value2):
        '''
        value1 이 우선순위가 높으면 -1 리턴
        value2 가 우선순위가 높으면 1 리턴
        두 우선순위가 같다면 0을 리턴
        '''
        # min_max == 1 ==> 최소 힙
        if self.min_max == 1:
            if value1 < value2:
                return -1
            elif value1 > value2:
                return 1
            else:
                return 0
        else:  # self.min_max == 2 ==> 최대 힙
            if value1 > value2:
                return -1
            elif value1 < value2:
                return 1
            else:
                return 0

    def __init__(self, s_min_max = 'min'):
        self.dynamic_arr = [None, ] # one based index, 다른 언어는 가변배열을 사용한다. C++은 백터 사용, 효율 좋게 짜는 것이 중요(가변배열이 수정시마다 매번 탐색, 복사, 삭제를 하면 메모리 낭비)
        self.num_of_data = 0 # 마지막 데이터의 index

        if s_min_max == 'max':
            self.min_max = 2
        else:
            self.min_max = 1

    def is_empty(self):
        if self.num_of_data == 0:
            return True

        return False

    def size(self): # ADT에 없는 함수이지만 테스트용으로 만듬
        return self.num_of_data

    # insert 메서드에서 사용
    # 부모 값과 비교해서, 우선순위가 부모 보다 높으면 True 낮으면 False
    def is_go_up(self, idx, data):
        if idx <= 1:
            return False

        parent_value = self.dynamic_arr[self.get_parent_idx(idx)]

        if self.get_prior(parent_value, data) == 1: # 부모 우선순위가 작다면
            return True
        else:
            return False

    def insert(self, data):
        if self.is_empty():
            self.dynamic_arr.append(data)
            self.num_of_data += 1
            return

        self.dynamic_arr.append(data)
        self.num_of_data += 1

        idx_data = self.num_of_data

        while self.is_go_up(idx_data, data):
            parent_idx = self.get_parent_idx(idx_data)
            self.dynamic_arr[idx_data] = self.dynamic_arr[parent_idx]

            idx_data = parent_idx

        self.dynamic_arr[idx_data] = data

    # 우선순위가 높은 자식 노드의 인덱스를 반환
    def which_is_prior_child(self, idx):
        left_idx = self.get_left_child_idx(idx)

        if left_idx > self.num_of_data:
            return None
        elif left_idx == self.num_of_data:
            return left_idx

        right_idx = self.get_right_child_idx(idx)

        left_value = self.dynamic_arr[left_idx]
        right_value = self.dynamic_arr[right_idx]

        if self.get_prior(left_value, right_value) == -1:
            return left_idx
        else:
            return right_idx


    def is_go_down(self, idx, data):
        child_idx = self.which_is_prior_child(idx)

        if not child_idx:
            return False

        child_value = self.dynamic_arr[child_idx]

        if self.get_prior(child_value, data) == -1:
            return True
        else:
            return False

    def delete(self):
        if self.is_empty():
            return None

        ret_data = self.dynamic_arr[1]
        last_data = self.dynamic_arr[self.num_of_data]
        self.num_of_data -= 1

        idx_data = 1

        while self.is_go_down(idx_data, last_data):
            child_idx = self.which_is_prior_child(idx_data)
            self.dynamic_arr[idx_data] = self.dynamic_arr[child_idx]
            idx_data = child_idx

        self.dynamic_arr[idx_data] = last_data
        self.dynamic_arr.pop()

        return ret_data




if __name__ == "__main__":
    heap = Heap("min")
    heap.insert(3)
    heap.insert(5)
    heap.insert(1)
    heap.insert(10)
    heap.insert(8)
    heap.insert(7)
    heap.insert(4)
    heap.insert(5)
    heap.insert(2)
    heap.insert(6)
    heap.insert(9)

    for i in range(1, heap.size()+1):
        print(heap.dynamic_arr[i], end = '  ')
        # 1  2  3  5  6  7  4  10  5  8  9  

    print("\n")

    for i in range(1, heap.size()+1):
        print(heap.delete(), end = '  ')       
        # 1  2  3  4  5  5  6  7  8  9  10   

 

우선순위 큐(PriorityQueue)

• heapq모듈 사용해 구현, 숫자가 높을수록 우선순위가 높다.
• 데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐와 달리, 우선순위 큐는 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거한다.

import heapq
 
class PriorityQueue():
    def __init__(self):
        self.queue = []
        self.count = 0
 
    def enqueue(self, priority, v):
        self.index += 1
        heapq.heappush(self.queue, (priority, self.count, v))
  
    def dequeue(self):
        heapq.heappop(self.queue)
 
    def display(self):
        print(self.queue)