Heap

[자료구조/C언어] 우선순위 큐 & 힙

1. What is Priority Queue(우선순위 큐란)?Queue(FIFO) 와 유사하다. 여기서 각 요소에 우선 순위가 있다는 것이 바로 Priority Queue라 한다. 2. How to implement a priority queue (어떻게 우선순위 큐를 구성할 것인가)?Heap-based implementation (우리는 이 방식을 쓸 것이다.)우선순위 큐 구성 방식특징a unsorted array/linked list요소를 마지막 위치에 삽입한다.우선 순위가 가장 높은 요소를 순차적으로 검색한다.임의 요소 삽입: O(1) / 최댓값 검색: O(n) / 최댓값 삭제 : O(n)a sorted array/linked list내림차순으로 요소를 삽입할 수 있다. 또한 첫번째 요소를 간단히..