힙 쏘트 (1) 썸네일형 리스트형 우선순위 큐 (priority queue), 힙 정렬 (heap sort) 우선순위 큐 (priority queue)- 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 된다.- 배열, 연결 리스트 등의 여러 가지 방법으로 구현이 가능한데, 가장 효율적인 구조는 heap이다. 배열을 사용하는 방법 1. 정렬이 안 되어 있는 배열의 경우삽입 시간 복잡도 \(O(1)\)삭제 시간 복잡도 \(O(n)\) 2. 정렬이 되어 있는 배열의 경우삽입 시간 복잡도 \(O(n)\)삭제 시간 복잡도 \(O(1)\) 연결 리스트를 사용하는 방법 1. 정렬이 안된 리스트- 삽입 시에 첫번째 노드로 삽입시키는 것이 유리하다. 다른 노드를 이동할 필요가 없다. 포인터만 변경하면 된다. 삽입 시간 복잡도 \(O(1)\)- 삭제 시에 포인터를 따라서 모든 노드를 뒤져보아야 한다. 삭제.. 이전 1 다음
