목록이진트리 (1)

나 JAVA 봐라

힙과 우선순위 큐

문득 JVM의 힙과 자료구조의 힙이 왜 이름이 똑같을까? 하는 궁금증이 생겼다가 자료구조 힙에 대한 개념을 다 잊어버려서 정리한다. 힙이란? 힙 : 데이터에서 최대값, 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙은 언제, 왜 사용해? 힙은 최대값, 최소값을 빠르게 찾기 위해 사용된다. 배열의 경우 최대값, 최소값을 찾는데 $O(n)$ 이 걸린다. 힙의 경우 최대값, 최소값을 찾는데 $O(logn$) 이 걸린다. => 따라서 최대값, 최소값을 찾기 위해 '힙' 을 사용한다. 우선순위 큐와 같이 최대값, 최소값을 빠르게 찾아야하는 자료구조, 알고리즘 구현에 활용된다. 즉, '힙' ..
CS/자료구조 2023. 12. 31. 18:37
이전 Prev 1 Next 다음