힙
-
알고리즘 기초 04) 힙 (Heap) 자료 구조Algorithm 공부자료/기본 알고리즘 정리 2020. 3. 12. 01:14
사전 개념 : 우선순위 큐 (Priority Queue) 자료 구조 우선 순위의 개념을 queue에 도입한 자료 구조이다. 데이터들이 우선 순위를 갖고 있으며, 우선 순위가 높은 데이터가 먼저 빠져나간다. 대표적인 사용처 : 시뮬레이션 시스템, 네트워크 트래픽 제어, CPU scheduling, 수치 해석적인 계산 등 구현 : list (array), linked list, heap 등으로 구현이 가능하며, 이 중 heap으로 구현하는 것이 가장 효율적이다. 개념 complete binary tree의 일종으로 우선순위 큐의 구현을 위해서 만들어진 자료 구조이다. 시간 복잡도 : O(logN) 여러 개의 값들 중에서 max 혹은 min value를 빠르게 탐색하기 위해서 만들어졌다. 중복된 값을 허용하지..