4.3 비선형 자료구조 (3)

우선순위 큐: 우선순위가 높은 데이터가 먼저 나오는 자료구조

 

*우선순위 큐의 구현 방식에 따른 시간 복잡도 (n: 노드 수)

구현 방법	삽입	삭제
배열	O(1)	O(n)
연결 리스트	O(1)	O(n)
배열	O(n)	O(1)
연결 리스트	O(n)	O(1)
힙	O(log n)	O(log n)

 

힙: 완전 이진 트리로, 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조

- 최대 힙: 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리

- 최소 힙: 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리

 

해시 테이블: 하나의 key에 대해 하나의 value을 저장하는 형태의 자료 구조 -> 평균적으로 O(1)의 시간 복잡도를 갖음

해시 충돌: 서로 다른 키에 대해 같은 해시가 도출되는 것

 

① 체이닝: 해시 충돌이 발생하면 같은 해시가 나오는 키의 값을 연결 리스트에 저장하는 방식

② 개방 주소법: 해시 충돌이 발생했을 때 해당 해시가 아닌 비어 있는 공간에 값을 저장하는 방식

- 선형 조사법: 다음 인덱스로 이동하면서 빈 공간을 찾는 방식

- 이차 조사법: 거듭제곱한 인덱스만큼 이동하여 빈 공간을 찾으면 데이터를 저장하는 방식

- 이중 해싱: 해시 충돌이 발생하면 다른 해시 함수를 한 번 더 적용하는 방식