힙은 이진 트리로서 마지막 레벨을 제외하고 완전히 채워져 있으며 마지막 레벨은 왼쪽부터 채워져 있습니다.
힙의 모든 노드들은 다음 성질을 가지고 있습니다.
각 노드의 값은 자기 자식의 값보다 작다(크다). 만약 힙에 같은 값이 존재한다면 작다가 아닌 작거나 같다.(크거나 같다)
주로 힙은 O(1)으로 최댓값 또는 최소값을 얻기 위해 사용합니다.
배열이나 링크드리스트와 같은 선형 데이터 구조는 O(n)으로 최대 값 최소 값으로 알 수 있지만 이진 탐색 트리와 같은 비선형 데이터 구조는 O(log n)으로 알 수 가 있습니다.
힙은 배열 또는 링크드리스트로 구현을 할 수 있지만 주로 배열로 사용합니다.
힙 구조를 배열로 구현을 할때 다음과 같은 구조가 성립합니다.
자식 노드는 부모의 인덱스에 2배를 더해서 왼쪽일 경우 + 1 오른쪽일 경우 + 2라는 공식이 성립한다.(2 * index + 1(+ 2))
- 힙이 비었을떄 10을 첫번쨰 노드는 삽입만 합니다.
- 다음 23을 넣었을때 배열 마지막에 넣은 후 첫번째 노드와 비교합니다.
- 36을 넣었을때도 위와 동일한 작업을 합니다.
- 18을 넣었을때는 부모인 23과 비교해서 작기 때문에 부모와 교환을 합니다. 그리고 다시 그 부모와 비교를 해서 크기때문에 바꾸지 않습니다.
이런 식으로 하는 걸 코드로 구현하면 아래와 같습니다.
참고 링크
https://blog.bitsrc.io/implementing-heaps-in-javascript-c3fbf1cb2e65
