sujae03   3년 전

Heap은 BST를 바탕으로 구성이 되잖아요?

보통 BST를 구현할 때는 Linked List를 쓰는데,

Heap 코드는 거의 '배열' 기반으로 구현이 되어있더라구요..


Heap 구현할 때는 Linked List로 구현 하지 않고 배열로 구현하는 것이 일반적인 방법 인가요 ??

rdd6584   3년 전

히프는 완전트리기 때문에 배열로도 표현이 가능합니다.
그래서 배열로 표현하는 것이 더 간편하고 효율적이기 때문이지 않을까요?

deneb2016   3년 전

BST를 힙처럼 사용할수는 있지만,

일반적으로 그렇게 쓰지는 않습니다.

성능, 구현 복잡도면에서 훨씬 간단한 방법이 있기 때문입니다..

힙은 완전이진트리 형태로도 구현할 수 있기 때문에,

일반적으로 BST가 아닌 배열 기반으로 구현합니다.

댓글을 작성하려면 로그인해야 합니다.