Heaps

A Heap is a binary tree structure with the following properties:

1. The tree is complete or nearly complete
2. The key value of each node is greater than or equal to the
   key value in each of its descendents (max-heap)
   -> Min-heap : the key value in a node is less than the key values in all of its subtrees

Heap은 Binary Search Tree를 알아보았다면, 굉장히 간단함을 느낄 수 있다.

BST의 경우는 현재 자신의 노드를 기준으로 left sub tree는 자신보다 작은 값을, right sub tree는 자신보다 큰 값을 가지도록 구성이 된다.

이에 반해 Heap은 현재 자신의 노드보다 sub nodes는 자신의 값 보다 작은 값을 가지도록 구성이 된다. 또한 추가로 항상 안정적이어야 한다. complete를 유지해야 하는데, 좌측 노드부터 add할 때 마다 채워진다고 생각하면 편하다.

여기서 중요한 점은 자식 노드들의 값의 우선순위는 없다!
그렇기에 다양한 tree들이 구성된다.

Heap에서는 reheap up과 reheap down을 알아볼 수 있는데,

• reheap up
  단순히 노드가 추가되는 경우 값이 크다면 점점 위로 올라가며(순서를 바꿔가며) 자리를 찾아가는 것이다.

• reheap down
  노드를 삭제했을 때, 가장 아래 있는 노드값이 위로 올라온 후 다시 순서를 바꿔 나가며 자리를 찾아가기만 하면 된다.

그리고 마지막으로 인덱스가 어떻게 구성되는 지 살펴보자.

인덱스는 부모 노드의 인덱스값x2+1,2 로 구성된다. 이를 통해 한 노드는 최대 두 개의 링크를 가지며 인덱스를 할당해 놓는 것이다.