힙(heap)에 대한 설명으로 가장 옳지 않은 것은? | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 자료구조론] 26년 1회차
힙(heap)에 대한 설명으로 가장 옳지 않은 것은?
1
최대 힙은 키값이 가장 큰 노드를 찾기 위한 완전 이진 트리로서 부모 노드의 키값이 자식 노드의 키값보다 항상 크거나 같고, 최소 힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 작다.
2
삽입 연산 시 노드가 개인 완전 이진 트리에서 다음 노드의 확장 자리는 번의 노드이며 그 자리에 삽입할 원소를 임시 저장한다.
3
일반적인 힙의 삭제 연산 시 루트 노드에 있는 원소를 삭제한다.
4
힙을 구현할 때 1차원 배열의 순차 자료구조를 이용하면 인덱스 관계를 이용하여 부모 노드를 찾기가 쉽다.
해설
최소 힙은 부모 키값이 자식 키값보다 작거나 같으면 되므로, "항상 작다"고 한 설명이 옳지 않다.
힙은 같은 키값을 허용하므로 최대 힙(부모 ≥ 자식)과 마찬가지로 최소 힙도 등호를 포함한 부모 ≤ 자식 관계를 만족한다.
- 삽입 시 완전 이진 트리를 유지하려면 마지막 노드 다음 자리( 위치)에 원소를 임시로 두고 부모와 비교하며 올라간다.
- 힙의 삭제는 루트 원소를 꺼낸 뒤 마지막 노드를 루트로 옮겨 재정렬한다.
- 배열로 구현하면 노드 의 부모는 처럼 인덱스 계산으로 바로 찾는다.
오류나 개정된 내용이 보이면 알려주세요