priority queue
-
[LeetCode] Longest Consecutive Sequence알고리즘 2019. 12. 6. 21:54
문제 Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Example: Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. Approach 배열이 sorting되어있으면 아주 쉽다. priority queue를 활용한 heap에 배열을 옮겨 담고 하나씩 빼면서 연속인지 아닌지 확인하면 됨 하지만 이 방법은..
-
Priority Queue자료구조 2019. 9. 2. 16:44
Max priority queue: root의 값이 가장 크고 자식의 값은 부모보다 작거나 같은 Tree Min priority queue: root의 값이 가장 작고 자식의 값은 부모 보다 크거나 같은 Tree empty(), size(), insert(), top(), delete()등의 기능이 있음 empty(), size(), top()은 O(1), insert()와 delete()는 O(logn) Binary 형태의 Priority queue는 Heap Sort에 사용됨 (Average, best, worst O(nlogn) Job Scheduling Problem에서 LPT algorithm 에 사용됨 (Max priority queue로 가장 긴 일을 골라 Min priority queue로..