(이코테) 자료구조 정리

우선순위 큐와 힙

우선순위 큐

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용합니다.
  ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우

자료구조	추출 되는 데이터
스택	가장 나중에 삽입된 데이터
큐	가장 먼저 삽입된 데이터
우선순위 큐	가장 우선순위가 높은 데이터

• 우선 순위 큐를 구현하는 방법
  1) 리스트를 이용
  2) 힙을 이용

우선순위 큐 구현 방법	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙	O(logN)	O(logN)

• 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일(힙 정렬)
  • 이 경우 시간 복잡도는 O(NlogN)

힙의 특징

• 힙은 완전 이진 트리 자료구조의 일종
• 힙에서는 항상 루트 노드를 제거
• 최소 힙
  -루트 노드가 가장 작은 값을 가짐
  • 따라서 값이 작은 데이터가 우선적으로 제거
• 최대 힙
  • 루트 노드가 가장 큰 값을 가짐
  • 따라서 값이 큰 데이터가 우선적으로 제거

우선순위 큐 라이브러리를 활용한 힙 정렬 구현 예제

import sys
import heapq
input=sys.stdin.readline

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
    

n=int(input())
arr=[]

for i in range(n):
  arr.append(int(input()))

res=heapsort(arr)

for i in range(n):
  print(res[i])

트리 자료구조

벨만 포드 알고리즘

바이너리 인덱스 트리

최소 공통 조상 알고리즘