목록힙 (1)

진강이의 성장일지

[자료구조] 우선순위 큐와 힙2

힙의 구현에 어울리는 것은? 연결리스트 아니라 배열앞서 우선순위 큐의 구현에 어울리는 것은 힙으로 결론이 났다.그렇다면 힙의 구현방법에 대해서 고민해보자. 힙은 트리이고 트리를 구현하는 방법에는 배열과 연결리스트가 있다. 이 둘 중 뭘 이용해야 할까? 정답은 배열이다.완전 이진 트리의 구조를 갖고 또 그 구조를 유지해야 하는 힙은 배열 기반으로 구현해야 한다. 연결리스트를 기반으로 힙을 구현하면, 새로운 노드를 힙의 '마지막 위치'에 추가하는 것이 쉽지 않기 때문이다. 배열 기반 힙을 구현하려면?배열을 기반으로 투리를 구성하는 방법을 요약하자면 다음과 같다.노드에 고유의 번호를 부여한다. 그리고 그 번호가 각 노드의 데이터가 저장 될 배열이 인덱스 값이 된다. 위 문장을 그림으로 설명하자면 다음과 같다...
소프트웨어학/자료구조 2024. 5. 14. 02:09
이전 Prev 1 Next 다음