생초보 자료구조(힙, 연결리스트, 배열, 우선순위 큐)에 대한 질문

Question

안녕하세요 군복학하고 개강을 앞두고 있는 컴공과 학생입니다'c&#43;&#43;로 쉽게 풀어쓴 자료구조'라는 책을 사용하여 공부중인데, 궁금한 점이 있습니다 우선순위 큐를 구현할 때에, 연결리스트로 구현을 할 때와 힙으로 구현을 할 때에 힙이 더 빠르다고합니다연결리스트는 정렬 여부에 따라서 삽입에 o(n), 삭제에 o(1) 또는 삽입에 o(1), 삭제에 o(n)힙은 삽입에 o(log2 n), 삭제에 o(log2 n) 이렇게 시간이 걸린다는것까지는 알겠습니다배열로 우선순위 큐를 구현해도 연결리스트와 같은 시간이 걸린다는것도 공부를 했습니다 힙은 완전 이진트리이고, 중간에 비어있는 요소가 없어서 배열로 구현하는것이 효율적이라고 합니다저는 이것을 같은 배열로 힙의 구조를 적용시킨 결과물이 시간이 적게 걸린다는 이야기로 이해했고, 연결 리스트(또는 이중 연결리스트)로 힙의 구조를 적용시키면 더욱 속도가 빨라지는지에 대해 궁금합니다 제가 공부하는 책에서는 정렬된 연결 리스트를 예시로 들고 있습니다여기서는 삽입시에 우선순위 값을 기준으로 삽입위키를 찾아야 해서 o(n)이라 합니다삽입 &#61; 반복{ 비교(우선순위 값) true시 값 삽입 후 반복 종료 }그런데 이 연결리스트를 힙처럼 정렬하고 힙과 같이 동작시킨다 생각해보면삽입 &#61; 삽입(맨 끝단) 후 반복{ 비교(자신 위치/2 위치의 부모노드) 자신이 더 크면 자신위치와 부모위치 노드를 서로 교환 } 이런경우에는 배열에는 없는 지연요소가 좀 있습니다일단 반복문을 사용해서 끝단을 찾아야함(last 위치 지정을 따로 하여 해결 가능)노드의 위치가 어디인지에 대한 측정이 필요함(반복문 등을 통해서)이런 문제점을 가지고도 배열과 같이 힙 구조를 통해 시간을 단축시킬수 있는지, 오히려 지연이 되는지 궁금합니다 ...더불어 연결리스트에 힙 구조가 안맞는다면 힙 구조는 무조건 삽입 가능한 자료량의 한계를 가지고 있는지도 궁금합니다

MKRO · Accepted Answer

'그런데 이 연결리스트를 힙처럼 정렬하고 힙과 같이 동작시킨다 생각해보면' 이 부분 읽었을 때 당연히 각 노드가 엣지 두개(left child, right child)를 가지게 해서 이진트리 구현할 줄 알았는데..링크드 리스트 정의가 무조건 엣지가 하나여서 일렬로만 연결되야하는건가요?? 만약 그렇다면 질문자님이 하신 말이 맞겠네요 힙 구현하려면 배열로 구현하는 방법이랑 엣지 두개인 노드로 구하는 방법(그럼 이건 뭐라고하죠?)이 있을 거 같네요.근데 후자의 경우 삭제시에 마지막 엘리먼트를 끌어온 다음에 정렬해야되는데 마지막 엘리먼트에 접근이 배열구현처럼 O(1)에 되기 힘들 것 같고요힙 자료량을 굳이 동적으로 하고 싶으면 배열을 동적배열로 관리하면 될 것 같은데요

seintcat · Answer

아하 동적배열이 있었군요!확실히 이중 연결 리스트보다는 그쪽이 낫겠네요

생초보 자료구조(힙, 연결리스트, 배열, 우선순위 큐)에 대한 질문

2개의 답변

Q&A 목록