C 자료구조/Heap
-
최대 힙 - BasicC 자료구조/Heap 2020. 6. 28. 00:59
들어가기에 앞서, 책 와 인용 1. 힙의 개념 힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 히프 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않았다.) 힙의 목적은 삭제 연산이 수행될 때마다 가장 큰 값 혹은 가장 작은값을 찾아내기만 하면 되는 것이다. 힙은 2가지가 있다. 부모 노드의 키값이 자식노드의 키값 보다 큰 최대 힙 반대로 부모 노드의 키값이 자식 노드의 키값 보다 작은 최소 힙이 있다. (위의 2가지 힙은 단지 부등호만 달라지고 나머지는 완전히 동일하다.) 힙은 완전 이진 트리이다. 여기서는 구현의 방식은 최대 힙으로 할 것이다. 값이 곧, 우선 순위이다. 값이 클수록 우선 순위는 높다. [아래의 그림..