[자바스크립트 자료구조] 힙(Heap) - (1) 최소힙, 최대힙 구현

힙(Heap) 힙이란? 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 힙에는 최소힙과 최대힙이 있음 최소힙 작은 값을 항상 트리의 위에 있게 해서 트리의 루트에는 가장 작은 값이 오도록 함 최대힙 가장 큰 값이 맨 위에 오도록 함. 모든 노드는 자기 부모 노드가 자기보다 큰 값을 가지고 있음 힙에 데이터를 삽입하고 값을 꺼내오는 방법 최소힙에 데이터를 삽입하는 방법 저런 트리가 있다고 하자 1을 삽입하려고 할 때 완전이진트리의 요건을 만족시키기위해 저 자리에 삽입 자신의 값과 자신의 부모노드값을 비교하여 자신의 값이 더 작으면 자리를 바꿈 3번의 과정을 자신의 값이 부모노드값보다 작을때까지 혹은 루트에 도착할 때까지 반복한다. 이 작업은 밸런스가 맞춰져있..

2021.03.24