힙 자료구조와 데이터 입력, 삭제
- 완전 이진 트리, 힙
힙은 우선순위 큐를 위해 사용하는 자료구조이다. 완전 이진 트리 형태를 가진다.
우선순위 큐로 사용하기 위해 만들어지는 자료구조이기 때문에, 트리의 값 중 최댓값 혹은 최솟값을 구하기 위해서 사용한다.
힙은 루트로 갈수록 큰 값을 가지는 경우(루트가 트리의 최댓값을 가지는 경우)와 루트로 갈수록 작은 값을 가지는 경우(루트가 트리의 최솟값을 가지는 경우)로 나눌 수 있는데, 전자를 Max Heap, 후자를 Min Heap이라고 한다.
이 글에서는 Min Heap을 기준으로 설명하겠다. Max Heap의 경우에는 단순히 작은 값을 찾는 것을 큰 값을 찾는 방식으로 거꾸로 진행한다고 생각하면 된다.
Min Heap은 부모의 노드 값이 항상 자식의 노드 값보다 작기만 하면 된다. 즉, 하나의 부모 자식 관계는 옆동네 부모 자식 관계와 아무런 상관이 없고, 이를 느슨한 정렬상태를 갖는다고 표현하는 듯 하다.
힙은 각각의 인덱스를 가지는 배열의 형태로 나타내어 코딩할 때 활용하는데, 위와 같이 1부터 10까지 순서대로 값을 가지는 힙이 있다고 한다면 이를 배열로 나타냈을 때는 아래와 같은 형태가 된다. 구현의 편의상 인덱스는 1번부터 시작하는 것이 관례적이다.
인덱스들을 트리에 표시하여 다시 트리를 그려보면 아래와 같다.
데이터와 인덱스가 공교롭게도 동일하지만, 여기서 말하고자 하는 것은 부모 노드와 자식 노드 인덱스의 관계이다.
그래프를 잘 보면 각각 두개의 자식 노드들은 본인 부모 노드의 x2 혹은 x2+1의 관계를 가지는 것을 알 수 있다..
따라서 이후에 알아볼 힙에서의 데이터 삽입과 데이터 삭제에서는 부모 노드의 인덱스를 i라고 한다면, i와 i*2, i*2+1노드를 비교하는 방식으로 진행한다.
- 힙에서의 데이터 삽입
Min Heap에서의 데이터 삽입을 알아보기 위해 위와 같은 그래프가 있다고 가정하자. 위의 그래프에서 데이터 1이 삽입되었다.
삽입된 데이터 1은 가장 마지막 인덱스에 삽입되어 부모 노드와 비교를 한다. 이 경우엔 삽입된 자식노드 1이 부모 노드인 9보다 작으므로 위로 올라가야 한다.
부모 노드였던 9와 1이 치환 되어 이젠 1이 부모 노드가 되었다.
마찬가지로 아직 Min Heap의 조건에 부합하지 않으므로 1의 부모 노드인 루트 노드와 비교한다. 이 경우에서도 1은 루트보다 작으므로 루트 노드와 치환되어야 한다.
모든 값 비교가 끝나고 Min Heap의 조건에 맞는 트리가 완성되었다.
- 힙에서의 데이터 삭제
데이터의 삽입은 가장 마지막 인덱스에 삽입된 데이터를 넣고 부모와 비교하며 치환을 반복했다. 그렇다면 데이터의 삭제는 어떻게 진행될까?
힙은 우선순위 큐 역할을 하기 위해 사용되는 자료구조이므로, 항상 최댓값 혹은 최솟값을 내어놓아야 한다. 지금은 Min Heap의 경우이기 때문에 항상 최솟값을 내놓아야 하고 결국 루트 노드가 삭제되어야 한다는 것을 알 수 있다.
루트 노드였던 1이 삭제되고, 가장 마지막 인덱스의 데이터를 루트로 옮겨놓는다.
그리고 데이터 입력할 때와 마찬가지로 Min Heap의 조건을 만족할 때 까지 부모 자식 노드를 비교하면 된다.
두 개의 자식 노드 중에서 어떤 노드와 비교할 지는, 둘 중 작은 노드와 비교하면 된다.
7과 3중에서 3이 더 작으므로, 3과 9를 비교해 치환하여 Min Heap의 조건을 만족시키고 치환이 종료된다.
힙 자료구조는 위와 같이 완전 이진 트리 특성을 갖기 때문에 N개의 데이터를 입력하거나 출력할 때 최악의 경우에도 O(logN)의 시간 복잡도를 보장한다는 장점이 있다.