힙을 array 기반으로 구현하는 이유

Question

안녕하세요. Heap 구현에 대해서 궁금해서 질문 드립니다. Heap 을 구현할 때, 트리는 보통 Linked List 로 구현하지만 Heap은 새로운 node를 힙의 '마지막 위치'에 추가해야하기 때문에 array 기반으로 구현해야한다고 하셨는데, 이 부분이 잘 이해가 되지 않습니다. Linked List든 Array List든 마지막 위치에 넣을 수 있는 건 똑같지 않나요?? 만약 size가 10인 Array List가 있고, 그 안에 [0, 300, 150, 170, 0, 0, 0, 0, 0, 0] 이렇게 3개의 node만 있다고 했을 때, 마지막 위치란 4번째 인덱스를 의미한다고 이해했습니다. 그랬을 때 Linked List도 4번째 인덱스에 insert하는 건 똑같다고 생각을 해서 이해가 잘 되지 않습니다. 답변 주시면 감사하겠습니다.

개발남노씨 · Answer

안녕하세요. jhappy님.  제 설명에 대한 보충설명과 함께, List와 Tree에 대한 내용을 좀 더 설명드려야 될 것 같습니다!     List라고 하면 Array를 이용한 구현과 Linked List 를 이용한 구현이 있죠. 그래서 자바의 경우에는 ArrayList, LinkedList를 간편하게 사용할 수 있습니다. 두 가지 종류의 List는 어쨋든 특징이 index를 이용해서 접근할 수 있도록 설계가 된 자료구조입니다. 물론 시간복잡도의 차이는 있겠죠.    제가 heap구현할 때 Array기반으로 구현해야된다고 했던 내용을 조금 수정보완해보자면, heap을 구현하기 위해서는 index를 사용하는 List기반으로 구현해야 합니다. 그 이유는 jhappy님께서 말씀해주셨듯이, array list든지 linked list든지 맨 마지막에 원소를 추가하는데 크게 어려움이 없기 때문입니다. (즉, jhappy님 말씀이 맞습니다! array list, linked list 어떤 걸로 구현하든지 둘다 좋습니다)   즉 아래의 그림은 배열(좀더 넓은 의미로 List)로 구현한 Heap입니다. Array List, Linked List 모두 List이므로 마지막 인덱스에 데이터를 추가하는게 쉽겠죠!!?     하지만 제가 설명에서 말씀드린 Linked list로 구현하면 힘들다고 한 내용은,  Tree를 구현할 때 흔히 사용하는 linked list 방식으로 하면 마지막 인덱스에 데이터 추가하는 일이 쉽지 않다고 말씀드린 겁니다.    즉 아래와 같은 트리를 구현하기 위해서는 Liked list 를 이용하여 트리를 구현해야 하는 것입니다. (주의할 점은 위에서의 Liked list는 List를 구현하기 위해 사용했고, 여기서 Linked list는 Tree를 구현하기 위해서 사용한 것입니다.) 이 경우 마지막 인덱스를 찾기가 쉽지가 않습니다.       이런 의미에서 저는 배열 vs linked list를 구분했는데, jhappy님께서 지적해주신것처럼 헷갈릴 수 있을 것 같습니다.   즉 수정해보자면   Heap은 Tree임에도 불구하고 List(array list & linked list; array list가 시간복잡도 관점에서 더 효율적)를 이용하여 구현합니다. 그 이유는 새로운 node를 힙의 &lsquo;마지막 위치&rsquo;에 추가해야 하는데, 이 때 List로 구현해야 이 과정이 수월해지기 때문입니다.     혹시 설명이 잘 됐을까요?? 잘 이해가지 않는 내용이 있다면 다시 질문 주시면 더 고심해보도록 해볼게요!!

jhappy · Answer

자세한 답변 덕분에 이해했습니다. 감사합니다!