#heap
노트 3개
Algorithm › Data Structure
힙과 우선순위 큐우선순위가 가장 높은 원소를 O(log n)에 넣고 꺼낼 수 있게 해 주는 완전 이진 트리 기반 자료구조, 편향되지 않는 이유와 힙 정렬, 크기 k짜리 힙으로 상위 k개를 O(n log k)에 구하는 방법.
Algorithm › Graph
다익스트라 최단 경로음이 아닌 가중치 그래프에서 한 정점으로부터 모든 정점까지의 최단 거리를 우선순위 큐로 구하는 알고리즘.
Algorithm › Graph
최소 신장 트리: 크루스칼과 프림가중치 그래프의 모든 정점을 사이클 없이 가장 싸게 잇는 최소 신장 트리와, 간선을 고르는 크루스칼·정점을 넓혀 가는 프림 알고리즘의 동작·복잡도·선택 기준, 결과가 늘 트리인 이유와 비연결 그래프의 최소 신장 숲.