힙(heap)이란 특수한 형태의 완전이진트리의 구조를 가진다.
힙은 각 노드의 키 값이(자식이 있다면) 그 자식의 키 값보다 작지 않은 완전 이진 트리이다.
힙의 구조를 살펴보면 아래와 같다.
완전 이진트리인 힙의 일반적인 형태
힙은 일반적으로 우선순위 큐(priority queue)를 구현할 때 자주 사용된다.
이전에 구현해 보았던 큐와는 달리 우선순위 큐에서는 우선순위가 가장 높은 원소를 먼저 삭제한다.
예를 들어 운영체제의 작업 스케줄러가 관리자에게 높은 우선순위를 부여하고 학생에게는 낮은 우선순위를 부여하는 우선순위 시스템을 사용한다고 가정하자.
이 경우 작업들을 유지하는 우선순위 큐를 최대 힙으로 구현할 수 있다.
힙은 우선순위 큐를 구현하는 한 방법일 뿐이다.
실제로 우선순위큐를 표현하기 위한 방법으로는 순서없는 배열, 순서없는 연결 리스트, 정렬된 배열, 정렬된 연결 리스트, 힙 등이 있다.
이 중 삽입과 삭제에 대한 복잡도가 둘다 log n의 복잡도를 가지는 것은 힙이다.
그렇기 때문에 우선순위큐를 표현하는 방법들중 힙을 선호하게 만든다.
그러면 힙의 삽입과 삭제 방법을 보도록하자.
아래 그림은 힙의 삽입 방법이다.
힙에서의 삽입 과정은 배열의 제일 뒤에 새로운 원소를 삽입하고 부모 노드의 키 값과 비교해서 부모 노드보다 작을 때까지 교체과정을 거친다.
즉, 삽입시에 최대한의 비교과정을 거치더라도 루트 노드까지만 비교하면 되므로 복잡도는 log n 을 따르게 된다.
다음은 힙에서 삭제가 일어나는 과정을 보도록 하겠다.
힙에서의 삭제 과정
힙에서의 삭제는 항상 루트의 값이 제거 되므로 루트의 값이 제거된 후에도 힙을 유지할 수 있도록 하기 위한 처리가 필요하다.
우선 완전 이진트리가 되어야 하므로 제일 뒤의 원소(여기서는 6)를 루트의 자리에 위치 시킨다.
그리고 힙의 특성상(여기서는 최대힙) 부모노드의 키값이 자식 노드의 키값보다 커야 하므로 자식 노드와 비교하면서 키값이 자식노드보다 클 때까지 반복해 나간다.
아래에는 힙을 구현하여 소스코드를 작성해 보았다.
Test.c
이올린에 북마크하기
이올린에 추천하기
TRACKBACK 1 AND
COMMENT 2
PREV
