코딩테스트 준비 with Python3/알고문센 정리
2023. 7. 8.
힙(Heap)이란?
힙(Heap)이란? 힙(Heap)이란 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리의 한 종류이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지하는데 최대 힙(max heap)의 경우 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크고, 최소 힙(min heap)의 경우 부모 노드의 키 값보다 항상 작다. 이진 탐색 트리에서는 중복된 값을 허용하지 않는 반면, 힙 트리에서는 중복된 값을 허용한다. 힙의 인덱스 값 힙의 인덱스를 잠시 보고 넘어가자면 최상위 부모 노드의 인덱스는 1, 그 다음 왼쪽 아래 자식 노드부터 2, 3 순서이다. - 부모 노드의 인덱스 = 자식 노드 인덱스 // 2 - 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 - 오른쪽 자식 노드의 인..
