최소-최대 힙의 정의 :
- 완전 이진 트리로서 공백이 아니면 각 원소는 키라 불리는 필드를 가진다.
- 트리의 각 레벨은 차례로 최소 레벨과 최대 레벨이 번갈아 나타나는데, 루트 노드는 최소 레벨이다.
- x가 최소 레벨에 있으면 x는 자신을 루트로 하는 부분 트리의 모든 원소들 중에서 최소 키값을 가지며, 이를 최소 노드라고 한다.
- x가 최대 레벨에 있으면 x는 자신을 루트로 하는 부분 트리의 모든 원소들 중에서 최대 키값을 가지며, 이를 최대 노드라고 한다.
최소-최대 힙의 구조 :
최소-최대 힙의 구조
최소-최대 힙에서는 삽입, 삭제의 연산이 필요하다.
삽입 연산의 경우 트리의 마지막에 새로운 노드를 추가하고, 그 추가된 노드가 최소에 해당하는 레벨인지 최대에 해당하는 레벨인지 확인 후 grandparent 노드와 비교해 가면서 적절한 위치까지 교환해 나간다.
반면, 삭제 연산의 경우 두 종류의 삭제 연산이 필요한데, 최소원소를 삭제하는 것과 최대원소를 삭제하는 것이다.
최소-최대 힙에서 필요한 연산들을 구현하였다. 첨부 파일에는 간단한 실행결과를 볼 수 있도록 display함수를 작성하여 결과를 확인 할 수 있도록 하였다.
Min_Max_Heap.c
이올린에 북마크하기
이올린에 추천하기
