Heap
완전 이진 트리(하나의 노드에 2개의 자식)의 일종으로 우선순위 큐(우선순위가 높은 데이터가 먼저 나가는 자료 구조)를 위하여 만들어진 자료이다.
힙은 반정렬 상태(느슨한 정렬 상태)를 유지한다.
항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다.
즉, 부모노드의 키 값이 자식 노드보다 항상 크거나 작은 트리다.
힙 정렬의 종류
힙의 종류에는 최대힙과 최소힙이 있는데 위에서 반정렬 상태를 설명할 때 크거나 작은 트리다. 라고 설명한 이유가 이것에 있다.
최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙: 부모 노드의 키값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
힙의 구현
힙을 저장하는 표준적인 자료구조는 배열
구현을 쉽게하기 위해서 배열의 첫번째 인덱스인 0은 사용되지 않으며 부모 노드와 자식 노드는 이런 관계를 가지게 된다.
왼쪽 자식의 인덱스 = (부모의 인덱스) 2
오른쪽 자식의 인덱스 = (부모의 인덱스) 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
내일(관련)해서 힙에 대한 알고리즘 구현을 해볼까 한다.
엉덩이
ㅇㅇ