대딩때 가장 즐겁게 만들었던 우선순위 Heap입니다.^^
참 단촐 하면서도 가장 재미있게 한 레포트였습니다.
항상 n-1을 유지 하기 때문에 Static 한 Arrary를 Pointer 이용하여 각 노드들의
포인터만 저장 될 수 있도록 하고 Indexing을 통하여 우선순위 Heap을 핸들링 하는 것이
좋겠다 생각 한다.
Push와 Pop을 이용하여 새로운 Node를 삽입하게 되고
삽입 된 노드는 항상 가장 아래에 입력이 됩니다. 즉 N-1에 입력이 된다고 할 수 있다.
Pop이 이루어질 때는 우선 순위가 갖아 높은 최상의 Node가 Pop이 되고
Pop이 되면 자식 노드중 가장 큰 값을 다시 최상으로 올리는 재배열이
이루어져야 한다.
요것만 지켜지면 Max Heap이 됩니다.
아래 내용은 내용의 출처는
http://timenote.net/ 에 기록자 님의 작성한 원문이다.
특별히 저자분의 동의 없이 내용을 훔쳐 왔다는게 마음에 걸리고 동의를 받아야 하겠다.
힙(heap)이란 특수한 형태의 완전이진트리의 구조를 가진다.
힙은 각 노드의 키 값이(자식이 있다면) 그 자식의 키 값보다 작지 않은 완전 이진 트리이다.
힙의 구조를 살펴보면 아래와 같다.
완전 이진트리인 힙의 일반적인 형태
힙은 일반적으로 우선순위 큐(priority queue)를 구현할 때 자주 사용된다.
이전에 구현해 보았던 큐와는 달리 우선순위 큐에서는 우선순위가 가장 높은 원소를 먼저 삭제한다.
예를 들어 운영체제의 작업 스케줄러가 관리자에게 높은 우선순위를 부여하고 학생에게는 낮은 우선순위를 부여하는 우선순위 시스템을 사용한다고 가정하자.
이 경우 작업들을 유지하는 우선순위 큐를 최대 힙으로 구현할 수 있다.
힙은 우선순위 큐를 구현하는 한 방법일 뿐이다.
실제로 우선순위큐를 표현하기 위한 방법으로는 순서없는 배열, 순서없는 연결 리스트, 정렬된 배열, 정렬된 연결 리스트, 힙 등이 있다.
이 중 삽입과 삭제에 대한 복잡도가 둘다 log n의 복잡도를 가지는 것은 힙이다.
그렇기 때문에 우선순위큐를 표현하는 방법들중 힙을 선호하게 만든다.
그러면 힙의 삽입과 삭제 방법을 보도록하자.
아래 그림은 힙의 삽입 방법이다.
힙에서의 삽입 과정은 배열의 제일 뒤에 새로운 원소를 삽입하고 부모 노드의 키 값과 비교해서 부모 노드보다 작을 때까지 교체과정을 거친다.
즉, 삽입시에 최대한의 비교과정을 거치더라도 루트 노드까지만 비교하면 되므로 복잡도는 log n 을 따르게 된다.
다음은 힙에서 삭제가 일어나는 과정을 보도록 하겠다.
힙에서의 삭제 과정
힙에서의 삭제는 항상 루트의 값이 제거 되므로 루트의 값이 제거된 후에도 힙을 유지할 수 있도록 하기 위한 처리가 필요하다.
우선 완전 이진트리가 되어야 하므로 제일 뒤의 원소(여기서는 6)를 루트의 자리에 위치 시킨다.
그리고 힙의 특성상(여기서는 최대힙) 부모노드의 키값이 자식 노드의 키값보다 커야 하므로 자식 노드와 비교하면서 키값이 자식노드보다 클 때까지 반복해 나간다.
아래에는 힙을 구현하여 소스코드를 작성해 보았다.
그럼 고운하루... 되세요.
