👉힙이란?
우선 힙(Heap)은 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 입니다.
- 완전 이진 트리
1) 마지막 레벨을 제외 하고 모든 레벨이 완전히 채워져 있다.
2) 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
3) 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조입니다.
힙(Heap)은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지합니다. 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
힙 트리에서는 중복된 값을 허용합니다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
👉힙(Heap)의 종류
1. 최대 힙(max heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
2. 최소 힙(min heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
👉힙(Heap)의 데이터 삽입
- 힙(Heap)은 완전 이진 트리이기 때문에, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워집니다
1. 15를 왼쪽 최하단 노드에 삽입
2. 10을 윈쪽 최하단 노드에 삽입후 부모와 비교
3. 부모보다 작으므로 그 자리에 위치시킨다.
4. 8을 삽입해야하는데 이미 왼쪽 노드에 데이터가 있으므로 오른쪽 최하단 노드에 삽입, 부모와 비교, 작으므로 그 자리에 위치시킨다.
힙(Heap)의 데이터 보다 클 경우
완전 이진트리의 구조에 맞게 최하단부 노트부터 채워지며 위치한 노드에서 부모노드와 값을 비교후 부모 노드보다 크다면 위치를 swap한다
1. 20을 왼쪽 최하단부 노드에 삽입한다.
2. 20의 부모 노드인 8과 비교한다. 20이 더 크므로 8과 위치를 바꾼다.
3. 20의 부모 노드인 15와 비교후 20이 더 크므로 15와 위치를 바꾼다.
👉힙(Heap)의 데이터 삭제
힙(Heap)은 가장 큰 값인 부모 노드의 값이 삭제된다.
1. 부모 노드값 삭제
2. 비어있는 부모노드에 최하단부 노드를 루트로 옮긴다.
3. 자식 노드와 비교후 루트보다(8) 크다면 바꾼다.
-왼쪽,오른쪽 자식 노드 둘 다 크다면 둘중에 큰 값을 부모 노드와 바꾼다.
우선순위 큐를 힙(Heap)을 이용해 구현하는것은 다음에 알아보도록 하겠다.
알고리즘+자료구조, CS지식 정리