Heap
-
[LeetCode] Merge k Sorted Lists알고리즘 2019. 9. 28. 20:39
문제 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 Approach Min heap에 list의 앞부분을 하나씩 담은 후 answer list에 min heap의 맨 위 원소를 넣어준다. answer에 들어간 원소는 next가 null이 아닌 경우 그 다음 원소를 다시 min heap에 넣는다. Code https://github.com/chi3236/algorithm/blob/master/LeetCode_MergeKSortedLists_MinH..
-
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로..