데이터구조-힙(Heap)

*데이터구조-힙(Heap)

-그래프의 트리 구조 중 하나

-그래프 : 몇 개의 정점(node)이 간선(edge)으로 연결된 것

그래프

-힙은 우선순위 큐(priority queue)를 구현할 때 사용

-우선순위 큐 : 데이터 구조의 하나로서 데이터를 자유롭게 추가할 수 있지만, 데이터를 추출할 때 최솟값부터 순서대로 선택하여 추출함

-각 노드에 데이터가 저장됨

 

*힙(Heap)의 예(최솟값 구하기)

-힙의 각 노드에 적혀있는 숫자는 저장되어 있는 데이터이며 이 노드들은 최대 두 개의 자식 노드를 가질 수 있음

-노드는 위에서부터 채워지고 같은 층 에서는 왼쪽부터 채워짐

-힙에서 자식 노드의 숫자는 반드시 부모의 숫자보다 커야함

 

*힙에 데이터 추가하기

-데이터 추가 시 가장 아래층에 있는 왼쪽 노드부터 값을 채우고 가장 아래층이 모두 채워지면 새로운 층을 만들어 가장 왼쪽에 채움

-힙에 숫자 5를 추가하는 경우

-추가되는 수는 가장 아래층에 한 자리가 남아 있어 먼저 숫자 7옆에 저장됨

-자식의 숫자가 부모의 숫자보다 커야되므로 부모의 숫자6과 추가되는 숫자5는 서로 교환

-부모의 숫자가 가장 작게 되도록 반복

 

*힙의 데이터 꺼내기

-데이터 추출 시 최솟값부터 추출하기 때문에 가장 위에 있는 숫자가 먼저 추출

-가장 위에 있는 숫자를 추출하고 난 뒤 힙의 구조는 다시 정리됨

-힙의 구조 정리 시 가장 오른쪽 아래에 있는 숫자를 가장 위로 이동(6을 위로 이동시킴)

-위로 올라간 숫자는 부모 숫자가 되며 좌, 우에 가지고 있는 자식숫자와 비교하여 숫자 중 더 작은 쪽과 교환하며 반복

-6과 3교환 - 6과 4 교환

 

*힙의 사용

-힙은 항상 가장 위에 최솟값이 있으므로 데이터 수에 상관없이 최솟값 추출 가능

-힙 추출 후 재구축 시 가장 후미에 있는 데이터를 위로 올려 가져온 후 다른 자식과 비교, 계산시간은 트리의 높이와 비례하게 됨

-힙은 관리하고 있는 데이터 중 최솟값을 자주 추출해야 하는 경우에 편리함

 

 

 

 

 

 

---

이 포스팅에 작성한 내용은 이시다 모리테루, 미야자키 쇼이치, ⌜알고리즘 도감⌟, 김완섭 옮김, (주)제이펍, 2020 에서 발췌하였습니다.