[알고리즘] 우선순위 큐

우선순위 큐

• 정의 : 원소를 제거할 시, 가장 우선순위가 높은 원소를 제거
  

  

  우선순위가 가장 높은 원소를 제거

• 배열로 구현
  • 삽입 : O(1)
  • 삭제 : O(n)
    

    

• 힙으로 구현 (부모의 값이 항상 자식보다 작은 완전 이진 트리)
  • 삽입 : O(logn)
    • 삽입 : 가장 마지막 노드에 값을 삽입하고 우선순위를 맞게 정렬 - 정렬에 드는 시간 복잡도 O(logn)
      

      

      • heap.insert(4)를 통해서 4라는 값을 삽입하려고 함
      • 빈 노드의 위치에 삽입
      • 정렬을 통해 우선순위를 맞춤
  • 삭제 : O(logn)
    • 삭제 : 부모를 삭제하고 남은 노드를 우선순위에 맞게 정렬 - 정렬에 드는 시간 복잡도 O(logn)
      

      

      

      • heap.pop()을 통해서 2를 제거하려고 함
      • 먼저, 2를 제거
      • 가장 마지막 노드에 있는 값을 맨 위의 노드에 삽입
      • 이후, 정렬을 통해서 우선순위를 맞춤
• 코드 

class priorityQueue:
    '''
    우선순위 큐를 힙으로 구현합니다
    '''

    def __init__(self) :
        self.data = [0]

    def push(self, value) :
        '''
        우선순위 큐에 value를 삽입합니다.
        '''
        # 1. 데이터 삽입
        self.data.append(value)
        
        # 2. 부모자식 관계를 맞는 지 확인 
        # 위치를 저장해서 바뀐 후에도 계속 비교가 가능하도록 기록해야 함 
        index = len(self.data) - 1 
        
        # 루트일때인 경우 고려 (index == 1)
        while index != 1 : 
            # 부모자식 관계를 확인 
            # 부모의 위치 : 나누기 2했을 때 몫 
            if self.data[index//2] > self.data[index]:
                val = self.data[index//2]
                self.data[index//2] = self.data[index]
                self.data[index] = val 
                index = index//2
            else:
                break 
        

    def top(self) :
        '''
        우선순위가 가장 높은 원소를 반환합니다. 만약 우선순위 큐가 비어있다면 -1을 반환합니다.
        '''
        if len(self.data) == 1:
            return -1 
        else:
            return self.data[1]

    def pop(self) :
        '''
        우선순위가 가장 높은 원소를 제거합니다.
        '''
        
        if len(self.data) == 1:
            return 
            
        self.data[1] = self.data[-1]
        self.data.pop()      
        
        index = 1
        while True : 
            # 1. 자식이 없는 경우 
            # 2. 왼쪽에 자식이 있는 경우 
            # 3. 둘다 자식이 있는 경우 
            priority = -1 
            
            if len(self.data) - 1 < index*2:
                break
            # 위에서 안걸렸으면 왼쪽은 자식이 있는 것임 
            elif len(self.data) - 1 < index*2 + 1:
                if self.data[index*2] < self.data[index]:
                    temp = self.data[index]
                    self.data[index] = self.data[index*2]
                    self.data[index*2] = temp
                    index = index * 2
                else:
                    break
            else:
                if (self.data[index] > self.data[index*2]) or (self.data[index] > self.data[index*2+1]):
                    if self.data[index*2] < self.data[index*2+1]:
                        temp = self.data[index]
                        self.data[index] = self.data[index*2]
                        self.data[index*2] = temp
                        index = index * 2
                    else:
                        temp = self.data[index]
                        self.data[index] = self.data[index*2+1]
                        self.data[index*2+1] = temp 
                        index = index * 2 + 1
                else:
                    break 
        pass
                        
            
        

def main():
    myPQ = priorityQueue()

    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''
    myPQ.push(1)
    myPQ.push(4)
    myPQ.push(3)
    myPQ.push(2)

    print(myPQ.top())
    myPQ.pop()
    print(myPQ.top())
    myPQ.pop()
    print(myPQ.top())
    myPQ.pop()
    print(myPQ.top())
    myPQ.pop()
    print(myPQ.top())
    myPQ.pop()

if __name__ == "__main__":
    main()