Coding Test(Priority Queue, Heap)

우선순위 큐(Priority Queue)

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

- list를 이용한 구현

- heap을 이용한 구현

단순히 N개의 데이터를 heap에 넣었다가 모두 깨내는 작업은 정렬과 동일 == Heap Sort =>O(NlogN)

 

Heap

- Max value or Min value을 찾아내는 연산을 빠르게 하기위해 완전 이진 트리를 기본으로한 자료구조

- heap에서는 항상 root node를 제거

 

최소 힙(min heap)

- root node가 가장 작은 값을 가진다

- 값이 작은 데이터가 우선적으로 제거

 최대 힙(max heap)

- root node가 가장 큰 값을 가진다

- 값이 큰 데이터가우선적으로 제거

 

완전 이진 트리(Complete Binary Tree)

root node부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 Tree

최소 힙 구성 함수 : Min-Heapify()

(상향식) 부모 노드로 거슬러 올라가며,  부모보다 자신의 값이 더 작은 경우에 위치를 교체한다

 

Heap에 새로운 원소가 삽입될 때 ==> O(logN)

Heap에서 원소가 제거될 때 ==> O(logN)

1. 가장 마지막 노드가 root node 위치에 오도록 한다

2. 이후에 root node에서 하향식으로(더 작은 자식 노드로) Heapify()를 진행

 

 

 

 

 

import heapq

#heap에 원소추가
heapq.heappush(list, value)

#가장 작은 원소 삭제 후 값 return
value = heapq.heappop(list)

#list to heap ==> O(logN)
heapq.heapify(list)

 

최소 힙(Min heap)

import heapq

#오름차순 힙 정렬
#최소 힙
def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

최대 힙(Max Heap)

음수화 해준 값에 대해 최소힙으로 나타낸 후 pop()과정에서 다시 양수화를 해버리면 그 자체가 최대힙

import heapq

#내림차순 힙 정렬
#최대 힙
def heapsort(iterable):
    h = []
    result = []
    for value in iterable:
        heapq.heappush(h, -value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
    return result

 

특정 규칙으로 Heap 구조 만들기(최대힙도 적용)

heapq.heappush(heap, (abs(num), num))

print(heapq.heappop(heap)[1])

Heap을 tuple로 구성했을 때 맨 앞 숫자만 가지고 정렬하므로 특정 규칙으로 Heap구조를 만들 함수를 앞에 적어주고

pop을 할 때 본래의 값을 꺼내주려면 tuple의 2번째 항을 pop 해야하기 때문에 heapq.heappop(list)[1]을 해준다

 

 

K번째 Min/Max Value 구하기

import heapq

def kth_smallest(nums, k):
  heap = []
  for num in nums:
    heapq.heappush(heap, num)

  kth_min = None
  for _ in range(k):
    kth_min = heapq.heappop(heap)
  return kth_min

print(kth_smallest([4, 1, 7, 3, 8, 5], 3))

힙 정렬(Heap Sort)

import heapq

def heap_sort(nums):
  heap = []
  for num in nums:
    heapq.heappush(heap, num)

  sorted_nums = []
  while heap:
    sorted_nums.append(heapq.heappop(heap))
  return sorted_nums

print(heap_sort([4, 1, 7, 3, 8, 5]))

 

 

 

 

 

 

참고자료

https://www.youtube.com/watch?v=jfwjyJvbbBI

https://www.youtube.com/watch?v=AjFlp951nz0