반응형 PriorityQueue2 [자료구조] 우선순위큐(Priority Queue)에 사용되는 Heap 자료구조 서론 우선순위큐를 사용하며 이 자료구조를 정확히 이해하기 위해선 그 전에 힙을 완벽히 이해하여야 겠다는 생각이 들었다. 이전과 같이 모르는 것을 그냥 넘어가는 일이 없도록 하자. Heap Priority Queue 데이터에 가중치를 두어 가중치의 오름차순 또는 내림차순으로 정렬한 큐. 주로 시뮬레이션 시스템, 작업 스케줄링에 사용. 배열 또는 연결 리스트로도 구현이 가능하지만 힙 자료구조를 사용하는 것이 가장 효과적. 리스트를 사용하여 구현한 경우 삽입의 시간 복잡도는 O(1), 삭제의 시간 복잡도는 O(n). Heap을 사용하여 구현한 경우 삽입과 삭제 모두 시간 복잡도는 O(logN) Heap 자료구조의 개념 배열을 기반으로 한 완전 이진 트리로 구성. 일반적 이진 트리와 다르게 중복된 값을 허용. .. 2021. 10. 25. [Go] Heap 자료구조를 사용하는 우선순위 큐 (Priority Queue) 서론 Go 에는 Priority Queue가 없다. 심지어 Queue 조차 없다. 그 이유는 예상컨데 너무 쉽게 Queue라 불리우는 자료구조를 구현할 수 있기 때문이 아닐까 싶다. 아무리 쉽지만 이해하지 않고 사용한다면 쉽게 느껴지지 않을테다. 내가그랬다.. 우선순위큐를 사용해야한다면 다른 언어를 통해 알고리즘을 풀어버린 나약한 선택을 했다.. 간단히 공부를 하고보니 예전에 예제를 보며 왜 이 복잡한 일을 개발자에게 맡기는거야! 라고 생각했지만 그 정도로 복잡한 내용이 아니었다. 살펴보자. Priority Queue 란? FIFO(First In First Out)의 특징을 가지는 자료구조인 Queue. 이 Queue 자료구조에서 우선순위를 주어 힙을 통해 우선순위를 기준으로 O(nlogn)의 시간 복.. 2021. 10. 4. 이전 1 다음 반응형
