힙
-
힙 HeapComputer Science/자료구조 2023. 11. 21. 00:01
항상 완전 이진 트리 형태 -> 중복을 허용 -> 반 정렬 상태임 [= 부모 자식관계에선 정렬되어있지만, 형제끼리는 정렬되어있지않음] 최소값, 최대값을 빠르게 찾는데 유용 -> 최소힙 Min Heap , 최대힙 Max Heap -> 최소힙 : 부모 노드의 키 ≤ 자식 노드의 키 -> 최대힙 : 부모 노드의 키 ≥ 자식 노드의 키 Heap의 특성(같은 레벨에선 노드가 좌측부터 채워짐)으로 인해 보통 배열을 통해서 구현한다. Heap의 삽입 Min Heap을 예시로 함 트리의 가장 끝에 데이터 삽입 부모 노드와 키를 비교한 후 삽입된 키가 더 작을 경우 부모와 교체 (반복) Heap의 삭제 Min Heap을 예시로 함 항상 최상위 노드를 반환 & 삭제 가장 마지막 위치의 노드를 최상위로 옮김 자식 노드 중 ..