힙 정렬1 [C & Java] Heap 힙 힙 (Heap) 완전 이진 트리 기반의 더미와 모습이 비슷한 자료구조 여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조 부모노드의 키 값이 자식 도느의 키 값보다 항상 큰 이진트리를 말한다. 부모노드와 자식 노드간에(루트 와 서브트리 간에) 위와 같은 조건이 항상 성립한다. 중복된 값을 허용한다. (이진 탐색트리는 안됨) 다른 용어로 이야기하면 히프안에서 데이터들은 느슨한 정렬 상태를 유지한다. 즉 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도이다. 히프의 목적은 삭제 연산이 수행될 때마다 가장 큰 값을 찾아내기만 하면 되는 것이므로(가장 큰 값은 루트 노드에 있음) 전체를 정렬할 필요는 없다. 히프는 완전 이진 트리이다. 힙의 종류 최대힙(Max .. 2021. 5. 19. 이전 1 다음 728x90 반응형