heap

heap은 우선순위 큐 같은 곳에서 최대값이나 최솟값을 빠르게 찾아낼 때 쓰이는 알고리즘이다. 자료구조는 트리를 이용한다.

 

max-heap은 최댓값이 무엇인지만 알 수 있고 나머지 값들은 어떤지 모른다.

heap을 만들 때 heapify라는 과정을 거친다.

이 수를 heap 정렬을 이용하게 되면

이걸로 트리를 만들어본다.

트리는 배열 및 리스트로 구현이 가능하다. 배열로 구현할 시에는 

맨 위의 root는 0이 되고 왼쪽 자식 노드는 0 * 2 + 1로 오른쪽 자식 노드는 0 * 2 + 2로 접근하게 된다.

 

가장 큰 노드가 맨 위로 오게 하는 것이 max heap의 목적이다. 그러므로 root와 왼쪽, 오른쪽을 비교하고 만약 자식이 더 크다면 현재의 노드와 자식 노드의 값과 교환한다. 그리고 가장 큰 곳의 위치를 largest라고 하고 자식이 없게 될 때까지 재귀적으로 반복한다.

 

힙 삭제시 마지막 노드가 root로 들어가고 그 이후로 heapify를 진행한다.