목록자료구조 (1)
열심히 코딩 하숭!
우선순위큐 & 힙 | 자료구조실습 2주차 과제
* 성신여대 22-2학기 자료구조실습 수업시간에 배운 내용을 토대로 요약 정리한 글입니다 1. 우선순위큐 & 힙 1-1. 우선순위큐 (priority queue) 정의 - 우선순위가 가진 요소들을 저장하는 큐 - 우선 순위가 높은 데이터가 먼저 나가게 됨 구현 방법 1) 배열을 이용 (오름차순) - 삽입: O(1) - 삭제: O(n) => 오래 걸림 2) 연결리스트 (내림차순) - 삽입: O(n) - 삭제: O(1) => 오래 걸림 3) 힙을 이용한 구현 - 완전이진트리를 이용한 우선순위큐 구현 - 일종의 반 정렬 상태를 유지 - 삽입: O(logn) - 삭제: O(logn) => 비교적 효율적! 1) 2)보다 훨씬 유리하다 그렇다면 힙에 대해 더 자세히 알아보자! 1-2. 힙 (heap) 정의 - 부모..
학교 과제/2022-2 자료구조실습 과제
2022. 9. 18. 23:43