힙2 [자료구조] 히프 (Heap) 히프 (Heap) 루트 노드가 언제나 그 트리의 최대값 혹은 최소값을 가지는 완전 이진 트리 최대 트리 : 노드의 키 값이 자식 노드 키 값보다 크거나 같음 최소 트리 : 노드의 키 값이 자식 노드 키 값보다 작거나 같음 힙 최초 구성 시 시간 복잡도 : O($n log {n}$) 우선순위 큐를 만드는데 사용! 트리의 최대값, 혹은 최소값을 반환하는 것이 주된 기능 1. 최대 히프 (Max Heap) 완전 이진 트리 & 최대 트리 부모 노드 키값 >= 자식 노드 키값 루트 노드 : 최대값 언제나 최대값이 반환됨 2. 최소 트리 (Min Heap) 완전 이진 트리 & 최소 트리 부모 노드 키값 2020. 9. 15. [알고리즘] 이중우선순위큐 (프로그래머스 Level3) 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 기본적으로 우선순위큐는 Heap을 통해서 구현된다. 하지만 자바에는 기본적으로 PriorityQueue가 구현이 되어있으므로 우선순위큐 자체에는 신경쓸 필요가 없고, 이중우선순위큐라는 점에 주목해야한다. 이 말인 즉슨, 한 큐에서 최대값을 반환, 최소값을 반환하는 두 가지 작업이 동시에 가능해야된다는 점이다. Solution 우선 각각 최대값, 최소값을 반환하는 PriorityQueue 2개를 만들었다. 하지만 데이터를 삭제할 때, 2개의 큐를 모두 동기화시킬 필요가 있다. 때문에 HashMap을 사용했다. HashMap의 Key값은 삽입된 데이터, Value는 현재 큐에 들어있는 해당 데이터의 개수를 의미한다. 이 후에 삽입 때는 특별한.. 2020. 9. 8. 이전 1 다음
