인프런 커뮤니티 질문&답변
작성한 질문수
질문이있습니다 선생님!
작성
·
26
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요
.이미지와같이 맥스힙일때 190이 push되어 맨 아래 즉 말단 노드에 일단 추가되고 부모노드와 비교를 통해 스왑되다가 190이 위 이미지와같이 위치해있는 상황일떄
150 노드 하위에 60과 100이 존재하는데요, 150노드는 90과 같은 위치에 존재하는데 100이 90보다 큰값이어도 서로 스왑할 필요는 없이 저대로 존재하는게 맞는건가요?!
답변 1
0
안녕하세요, 인프런 AI 인턴입니다. alopp님.
힙 자료구조에 대해 질문을 주셨군요! 힙은 완전 이진 트리로, 각 노드가 부모 노드보다 작거나 같아야 하는 특성이 있습니다(맥스 힙의 경우). 190이 맥스 힙에 삽입되고 위치가 결정된 후, 150 노드의 자식들이 60과 100으로 결정된 상황에 대해 설명드리겠습니다.
맥스 힙의 구조
맥스 힙은 각 부모 노드가 자식 노드보다 큰 값을 가지는 이진 트리입니다. 즉, 한 노드의 값이 그 자식 노드의 값들보다 크다는 규칙을 유지합니다.
노드 스왑에 대한 설명
질문에서 주신 내용처럼, 150이 190보다 아래 위치하면서 60과 100을 자식 노드로 갖게 되는 경우에 대해 설명드리겠습니다.
이미지 링크를 보니 이해를 돕기 위해 무엇이 중요한지 설명드리겠습니다.
1. 노드 값 비교: 맥스 힙에서는 부모 노드의 값이 항상 자식 노드의 값들보다 커야 합니다. 자식 노드끼리는 비교하지 않습니다.
2. 스왑 여부: 부모 노드와 자식 노드를 비교하여 부모 노드의 값이 작다면 스왑이 일어납니다. 자식 노드끼리는 스왑을 하지 않습니다.
예시로 설명
주신 예시에서,
- 150 은 자식 노드로 60과 100을 가지게 되며, 150은 60과 100보다 큽니다.
- 따라서 힙 조건을 만족하며, 100과 90의 값 비교는 하지 않습니다. 이는 100과 90이 서로 다른 부모 노드의 자식이기 때문입니다.
아래 포럼 내 유사한 질문에 대한 설명도 도움이 될 것입니다. 더 자세한 설명이 필요하면 해당 링크들을 참고해 보세요:
- 힙을 array 기반으로 구현하는 이유
이미지와 원본 링크:
맥스 힙 상세 원본 링크
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.