![]()
언제 사용하나? 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료규조. 자료구조는? Priority Heap == Heap + Complete Binary Tree Binary Search Tree 와 달리 중복을 허용하고 같은 레벨의 노드간에는 정렬 되있지 않은 느슨한 정렬 상태를 유지한다. 주요 연산 및 시간 복잡도 Operation Time Complexity Insert (add) O (log N) Find (contains) O (N) Find2 (peek) O (1) Delete (poll, remove) O (log N) Delete2 (remove(element)) O (N) Binary Tree 인데 왜 Find 에 O(N) 이 걸리나? PriorityQueue.contai..
Complete Binaray Tree every level, all nodes are filled ordering left to right except possibly last node When to use? -> Implements Prirority Queue! * Full Binrary Tree : every node has two children ADT of Prirority Queue implements using MAX Heap array -> parent index : i / 2 left child index : i * 2 right child index : i * 2 + 1 maxSize: Capacity size: The number of current elements which heap..
![]()
🔒 문제 💭 생각의 흐름 MST (Minimum Spanning Tree) + Undirected Graph => 2가지 방법! Kruskcal Prim✔️ mstSet: 방문된 MST 원소의 집합 not visited Set: 아직 방문하지 않은 노드 번호 - 비용 집합 find minimum cut vertex : mstSet과 not visited Set을 최소 비용으로 연결하는 노드 찾기 mstSet -> 어차피 weight의 총합을 구하는 것이므로 방문 순서를 저장할 필요가 없겠다 -> unorderd_set not visited Set -> 배열로 생성시 따로 visited Boolean 배열이 필요하므로 map 자료구조 사용 ⭐ find minimum cut vertex -> not vist..
