Heaps

Heaps

• 이진트리의 한 종류로서, 이진 힙(binary heap) 이라고도 불린다.
• 힙에는 최대 힙(max heap), 최소 힙(min heap)이 존재한다. 최대 힙과 최소 힙은 데이터 원소의 순서 기준이 내림차순이냐 오름차순이냐만 달라지고 완전히 대칭한다.

Max heap

• 최대 힙은 다음 세 가지 성질을 갖는다.

  1. 루트 노드가 항상 최댓값을 가진다.
  2. 완전 이진 트리
  3. 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다. 이는 트리의 빈번한 재귀적인 정의

Binary Search Tree vs. Max heap

• 이진 탐색 트리에서는 원소들이 완전히 크기 순서대로 정렬되어 있다. 따라서 중위 순회를 하면 데이터를 정렬된 순서로 뽑아낼 수 있다.
• 최대 힙은 완전히 크기 순서대로 정렬되어 있지는 않다. 따라서 트리를 순회함으로써 데이터를 정렬할 수는 없다.
• 이진 탐색 트리에서는 루트 노드로부터 시작하여 특정 원소를 빠르게 검색할 수 있는 반면, 최대 힙은 이러한 탐색 연산을 제공할 수 없다.

Max heap 장점

• 완전 이진 트리 (complete binary tree) 여야 한다는 제약 때문에, n 개의 노드로 이루어진 최대 힙의 높이 (깊이) 는 log(n) + 1 (에서 소수 부분은 버림) 로 정해진다.

• 이 성질 때문에 데이터 원소의 삽입/삭제 연산의 실행 시간은 언제나 log(n) 에 비례한다.
  따라서, 어떤 최대 힙이 존재할 때, 이 힙으로부터 반복적으로 루트 노드를 삭제하면(서 데이터 원소들을 꺼내면) 루트 노드에 들어 있는 키가 힙 내에서 최대임이 보장되어 있으므로 데이터를 내림차순으로 정렬할 수 있고, 이 정렬에 소요되는 시간 또한 log(n) 에 비례한다.

• 힙이 항상 완전 이진 트리라는 성질은 트리의 표현에 있어서도 이점을 제공한다. 노드들에 번호를 매기면, 이 번호 순서로 이루어진 선형 배열에 트리를 표현할 수 있다. 또한, 완전 이진 트리이므로 노드의 추가와 삭제는 배열의 맨 마지막 원소에서만 일어난다.