[웹 프로그래밍 스쿨 20주차] 파이썬으로 우선순위 큐를 위한 heap 구현하기!

 

웹 프로그래밍 스쿨 20주 차 포스팅입니다!😃

 

 

이번 주에는 저번 주에 시작했던 자료구조 heap에 대한 수업을 마무리하고,

 

알고리즘의 설계 패러다임들에 대해 알아보고,

 

1. 완전탐색(brute-force, exhaustive search)

2. 분할정복(divide-and-conquer)

3. dp(동적 계획법)

4. 탐욕 알고리즘(greedy algorithm)

 

그 중 한 분류인 완전탐색에 관련된 문제들을 풀어보는 시간을 가졌습니다.

 

알고리즘 문제들이 이렇게 분류가 되어있는지 모르고 여태까지 뭔가 아이큐 테스트를 하는 느낌으로

문제를 풀어왔던게 좀 아쉬웠는데요 😂

 

기술면접을 위해서도, 좋은 코드를 짜기 위해서도 열심히 준비해두면 좋다는 강사님의 말씀이 있었지만..

 

아직 첫 수업만으로는 재귀함수도 익숙해지지 않아서 일단 자료구조 heap에 대해 먼저 정리 해봤습니다.

 

 

 

 

1. 자료구조 힙(heap)이란?

 

 

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한

자료구조로서 부모노드와 자식노드간의 키값 사이에는 대소관계가 성립합니다.

 

이 중 부모노드의 키값이 자식노드의 키값보다 작지 않은 힙을 max heap 이라고 하고

부모노드의 키값이 자식노드의 키값보다 크지 않은 힙을 min heap 이라고 합니다.

 

 

 

 

2 . 일반 큐(queue) 와 우선순위 큐(priority queue) 의 차이

 

 

• 일반 큐는 가장 먼저 들어온 데이터가 가장 먼저 나가는 FIFO 구조를 가지고 있고

• 우선순위큐는 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 나갑니다.

 

 

3. 우선순위 큐 ADT

 

 

 1) push(elem)

    element를 삽입하고 배열을 우선순위에 맞게 재정렬합니다.

 

 2) pop()

    우선순위가 가장 큰 원소를 삭제 후 반환합니다.

 

 3) top()

    우선순위가 가장 큰 원소를 삭제하지 않고 반환합니다.

 

 

4. 파이썬으로 우선순위 큐를 위한 max heap 구현하기

 

https://github.com/ythwork/

 

 

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

    @property
    def key(self):
        return self.__key
    
    @key.setter
    def key(self, k):
        self.__key = k

class MaxHeap:
    MAX = 1024
    def __init__(self):
        self.__heapsize=0
        # 배열을 사용한 힙 구현
        self.__container = [None for _ in range(MaxHeap.MAX)]
		
	# 부모와 자식노드의 인덱스를 구하는 내부 편의함수
    def __get_parent_idx(self, cur):
        return cur//2

    def __get_left_child_idx(self, cur):
        return cur * 2

    def __get_right_child_idx(self, cur):
        return cur * 2 + 1

 

 

간단하게 노드로 사용할 Element 클래스와 MaxHeap 클래스를 만들고 

 

현재의 노드를 기준으로 부모노드의 위치와 자식노드의 위치를 구할 수 있는 편의함수를 정의합니다.

 

 

    def is_empty(self):
        if self.__heapsize == 0 :
            return False
        else :
            return True

   def is_full(self):
        if self.heapsize >= MaxHeap.MAX:
            return True
        return False
    

 

 

    def push(self, key):
        if self.is_full():
            return 

        self.__heapsize += 1
        self.__container[self.__heapsize] = key
        cur = self.__heapsize
        par = self.__get_parent_idx(cur)

        while cur != 1:
            if self.__container[par] < self.__container[cur]:
                self.__container[par], self.__container[cur] =  self.__container[cur], self.__container[par]
                cur = par
            else :
                break

 

• 완전이진트리 형식을 유지하기 위해 heap 사이즈를 한칸 늘리고 마지막 인덱스에 노드를 삽입합니다.
  
  

• 삽입한 노드의 인덱스를 cur 에 할당하고 위에서 작성한 편의함수를 사용해 부모노드의 인덱스를 찾아
  par에 할당합니다.

 

 

https://github.com/ythwork/

 

 

• max heap의 두번째 조건인 부모노드가 자식노드보다 작지 않은 상태를 만들기 위해
  cur 과 par의 키값을 비교하고 자식노드가 더 크다면 부모노드와 위치를 바꿉니다.
  
  

• 더이상 자식노드가 부모노드보다 크지 않거나 cur이 루트노드의 인덱스인 1에 도달하기 전까지 반복합니다.

 

    # 자식노드 중 더 큰 값을 가지는 자식의 인덱스를 반환하는 편의함수
    def __get_bigger_child_idx(self, cur):
    
        if cur*2 > self.__heapsize:
            return None
        elif cur*2 == self.__heapsize:
            return cur*2
        else :
            if self.__container[cur*2].key > self.__container[cur*2+1].key:
                return cur*2
            else :
                return cur*2+1

 

    def pop(self):
        if self.is_empty():
            return
        
        ret = self.__container[1]
        temp = self.__container[self.__heapsize]
        cur_idx = 1
        bigger_child_idx = self.__get_bigger_child_idx(cur_idx)
        while bigger_child_idx and temp.key < self.__container[bigger_child_idx].key:
            self.__container[cur_idx] = self.__container[bigger_child_idx]
            cur_idx = bigger_child_idx
            bigger_child_idx = self.__get_bigger_child_idx(cur_idx)
            self.__container[cur_idx]=temp
        self.__heapsize -= 1
        return ret

 

• 우선순위가 가장 높은 값인 루트노드를 반환하기 위해 ret 변수에 할당해둡니다.
• 완전이진트리를 유지하기 위해 heap의 마지막 원소를 루트로 보냅니다.

 

https://github.com/ythwork/

 

• max heap의 두번째 조건인 부모노드의 키값이 자식노드 보다 작지 않다를 만족시키기 위해

  루트노드의 자식들의 키값을 비교하여 더 큰 값을 찾아냅니다.
  
  

• 더 큰 키값을 가지는 자식노드와 임시로 루트로 올린 노드의 키값을 비교하여 자식노드의 키값이

  더 크다면 서로 자리를 바꿉니다.

• 자식노드가 더이상 존재하지 않거나 부모노드의 키값이 자식노드의 키값보다 커질 때까지 반복합니다.
  
  

• 반복이 끝나면 heap_size를 줄여 배열을 작게하고 ret에 담아두었던 루트노드를 반환합니다.

 

 

 

웹 프로그래밍 스쿨에 대해 더 알아보기 ⭐