Hee's Story

숫자가 클 수록 우선순위가 높다는 문제에서 우선순위 큐를 내림차순으로 설정해서 사용하였다. 여기서 다음과 같은 이슈가 발생하였다. 우선순위 큐에 {3,7,6,2,4}를 넣었을 때 당연히 {7,6,4,3,2} 가 나올 줄 알았지만 {7,4,6,2,3}가 나왔다. 찾아보니 자바에서 우선순위 큐는 힙으로 구현되어있다는 것을 알았다. 이전에 정리했었는데..ㅎ 그래서 이번에는 제대로 이해하려고 한다. [자료구조] 힙(Heep) & 우선순위 큐 힙(Heep) 최댓값, 최솟값을 빠르게 찾기 위해 고안된 자료형으로 우선순위 큐를 위해 만들어졌다. 완전 이진 트리의 일종으로, 각 노드의 키값이 그 자식의 키 값보다 작지않거나(최대 힙), 크지 hee96-story.tistory.com 자바에서 우선순위 큐는 아래와 같이..

힙(Heep) 최댓값, 최솟값을 빠르게 찾기 위해 고안된 자료형으로 우선순위 큐를 위해 만들어졌다. 완전 이진 트리의 일종으로, 각 노드의 키값이 그 자식의 키 값보다 작지않거나(최대 힙), 크지 않은(최소 힙) 완전 이진 트리이다. 완전이진트리는 중복을 허용하지 않지만 힙은 허용한다. 우선순위 큐 우선순위가 있는 큐 가장 우선순위가 높은 데이터가 먼저 나간다. 배열, 연결리스트 힙 으로 구현이 가능하다. 힙으로 구현하는 것이 가장 효율적이다. 자료구조 삽입 삭제 정렬된 배열 / 순서 없는 배열 O(n) / O(1) O(1) / O(n) 정렬된 연결 리스트 / 순서 없는 연결리스트 O(n) / O(1) O(1) / O(n) 힙 O(logn) O(logn) 힙(Heap) 최대 힙(Max heap) 부모 노..