datastructure2 [자료구조] 우선순위 큐(Priority Queue)란? 우선순위 큐(PQ: Priority Queue)란? 기존의 큐는 먼저 들어온 순서대로 First In, First Out (FIFO)을 만족하지만, 우선순위 큐는 우선순위가 더 높은 원소에 대하여 IO 먼저 진행한다. 우선순위 큐(Priority Queue) 구현은 어떻게 할까? 일반적으로 힙(Heap)을 이용한다. (힙이란?) 배열이나 연결리스트를 사용하지 않는 이유는? (찬희님의 블로그) → 삽입 과정에서 소요되는 시간이 O(n)으로 비교적 길기 때문에 값이 클 수록 우선순위가 높다고 가정했을 경우, 아래와 같이 최대힙을 사용하여 우선순위 큐를 구현해 준다. 힙의 성질에 따라, n번째 노드의 자식들은 2n, 2n+1번째에 채워지게 된다. n번째 노드의 부모는 n / 2 번째에 위치한다. PQ의 Pus.. 2021. 11. 17. [자료구조] 힙(Heap)이란? 힙(Heap)이란? 완전 이진 트리로 이루어진 자료구조! (자식이 두개이며, leaf는 왼쪽부터 채워진다) 느슨한 정렬 상태를 유지한다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리 최대값(최소값)을 빠르게 찾을 수 있도록 한다. 종류 최대힙과 최소힙으로 구분할 수 있다. 최대힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 (부모 키 값 >= 자식 키 값) 최소힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 (부모 키 값 1; i /= 2) { if (heap[i / 2] > heap[i]) { swap(i / 2, i); } else { break; } } } 삭제 (Delete) Heap에서의 삭제는 Root 삭제.. 2021. 11. 16. 이전 1 다음
