23.06.30 자료구조 8. 힙(Heap)

힙은 트리의 일종으로 완전이진트리이다. 그러면 왜 힙을 또 따로 분리를 했을까? 트리랑은 뭐가 다를까? 했을 때 힙은 부모 노드와 자식 노드 간의 대소 관계가 확실하다. 예를 들어 부모노드가 더 큰 경우 전체 트리에서 부모노드는 항상 자식 노드보다 크며 반대의 경우에도 전체에 똑같은 규칙이 적용된다. 이러한 구조가 필요한 이유는 우선순위에 따른 작업을 하기 위해서이다. 우리도 살다 보면 우선적으로 먼저 해야 하는 일들이 있고 이것에 순서가 일정하지 않은 경우가 있다. 가장 나중에 들어온 일인데 가장 중요한 경우도 혹은 애매하게 10번째 들어온 일이 4번째로 중요한 일로 처리될 수도 있다. 그래서 이럴 때 힙을 사용하여 우선순위 큐를 만드는 게 가장 효율적이다. 우선순위 큐란 말처럼 큐와 비슷한 형태지만 가장 먼저 온 게 가장 먼저 나가는 게 아닌 우선순위에 따라  먼저 나가는 것이다. 이를 힙이 아니라 배열이나 연결리스트를 이용해서 만드는 것도 가능하지만 부모 노드와 자식 노드의 대소 관계가 전체에 적용된 힙이 가장 효율적이라고 한다.

 

이렇게 기본적인 자료 구조를 찾아보며 느낀 것은 어떤 자료구조를 대체할 수 없다라기 보다는 어떤 자료 구조가 어떤 때에 효율적이냐 그리고 자료 구조가 각각 독립적인 것이 아니라 이런 부분이 더 특화되면 좋겠어라고 하는 필요성에 의해서 다른 자료구조에서 파생되거나 분리해서 명칭이 생기는 것 같다.