- 힙
- ==힙은 최대값 혹은 최소값을 빠르게 찾기 위한 이진트리입니다. 최소힙은 부모는 자식보다 작고 최대힙은 부모는 자식보다 커야됍니다. 힙의 삽입과 삭제는 O(log’2’N) 만큼 곧 높이의 시간복잡도를 갖습니다.
- insert(), delete(루트노드가 대상), peek
- 높이 만큼 시간복잡도 (로그N(원소수))
- log’2’8 = 8을 나오게만드는 2의 지수를 구하는 것
- 새값 추가는 맨 말단 왼쪽부터 넣고, 바로위 부모랑 크기 비교하며 자리 스위칭
- 삭제는 맨 머리에 있는것과 발에 있는것을 바꿈, 그 뒤에 발에 있던 최소값 지우고, 새로온 머리와 자식크기 비교하며 자리바꿈 (높이 만큼 시간복잡도 (로그N))
- Priority Queue에 대해서 설명해주세요.
- ==추상데이터 타입으로, 구현체는 힙이 있음. 우선순위가 높은 아이템이 먼저 처리됌, insert때 우선순위정보 포함, delete 우선순위대로 뽑고 지움, peek 뽑느데 지우진 않음. 힙이 성능이 제일 좋은 구현체임.
- ==힙은 최대값 혹은 최소값을 빠르게 찾기 위한 이진트리입니다. 최소힙은 부모는 자식보다 작고 최대힙은 부모는 자식보다 커야됍니다. 힙의 삽입과 삭제는 O(log’2’N) 만큼 곧 높이의 시간복잡도를 갖습니다.
