목록힙 (1)

FE PARADISE

[자료구조] 힙 Heap 자바스크립트(Javascript)로 구현하기

힙 Heap 이란? 최댓값과 최솟값을 찾아내는 연산을 빠르게 수행하고자 고안된 이진트리 기반 데이터 구조이다. 삽입과 삭제 시 O(log n)의 시간복잡도를 가진다. 최대 힙 Max Heap 상위 노드에 제일 큰 값이 위치한다. 위의 트리구조 힙을 배열로 나타내면 아래와 같다. 부모 노드 인덱스 & 자식 노드 인덱스 구하기 부모 노드 인덱스 : 자식 노드 인덱스 / 2 왼쪽 자식 노드 인덱스 : 부모 노드 인덱스 * 2 + 1 오른쪽 자식 노드 인덱스 : 부모 노드 인덱스 * 2 + 2 삽입 기존의 최소 힙에 새로운 값 17을 삽입한다고 해보자. → 코드 상에서 add(17)에 해당 위와 같이 마지막 노드의 왼쪽부터 삽입할 노드를 추가한다. 그 후 부모 노드와 크기를 비교하며 정렬해나간다. → 코드 ..
자료구조 & 알고리즘 2023. 8. 29. 00:39
이전 Prev 1 Next 다음