최대 힙2 [알고리즘] ep1-3) 힙(heap) *완전 이진 트리(Complete Binary Tree): 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리 ㅁ힙(heap): 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 완전 이진 트리의 일종 + 영단어 heap: 무엇인가를 차곡차곡 쌓아 올린 더미+ 자료구조의 힙(Heap)과 컴퓨터 메모리의 힙 영역(Heap Area)은 완전히 다른 개념이다 [힙의 활용]우선순위 큐(Priority Queue): 힙을 사용하여 구현할 수 있으며, 각 요소가 우선순위를 가지는 큐힙 정렬(Heap Sort): 힙을 이용한 정렬 알고리즘으로, O(nlog(n))의 시간 복잡도를 가진다그래프 알고리즘: 크루스칼 알고리즘, 다익스트라 알고리즘 등에서 우선순위 큐를 활용해 최소 신장 트리,.. 2024. 7. 3. [알고리즘] ep1-1) 우선순위 큐 ㅇ우선순위 큐(Priority Queue): 각 요소마다 우선순위를 부여하고 이 우선순위에 따라 요소를 처리하는 큐요소가 삽입될 때 우선순위가 함께 부여되며, 삭제 시에는 가장 높은 우선순위를 가진 요소가 먼저 삭제된다 활용 분야: CPU 작업 스케줄링, 네트워크 패킷 처리, 최단 경로 알고리즘(다익스트라 알고리즘 등) 등 [구현 방법 2가지]1. 리스트를 이용한 구현① 무순리스트로 구현: 리스트에 임의 순서로 저장e.g. 선택정렬 ② 순서리스트로 구현: 리스트에 키 정렬 순서로 저장e.g. 삽입정렬 2. 힙을 이용한 구현① 최대 힙 사용② 최소 힙 사용 일반적으로 우선순위 큐를 구현할 때는 힙을 사용하는 것이 가장 효율적이다(최대 힙 or 최소 힙) 출처 및 참고: 알고리즘-원리와.. 2024. 7. 3. 이전 1 다음
