[알고리즘] 힙과 우선순위 큐, 둘의 차이점

힙 최대 힙은 완전 이진트리이고, 부모가 항상 자식보다 큰 자료구조이다. 완전 이진트리란, 마지막 레벨을 제외하고 모든 레벨의 노드가 다 채워져 있고 마지막 레벨은 왼쪽부터 채워지는 트리이다. 최소 힙은 반대로 부모가 항상 자식보다 작다. 힙은 완전 이진트리의 특성상 부모와 자식의 index가 명확해서 배열을 사용한다. A[i]의 부모는 A [i/2]이고 왼쪽 자식은 A [2*i] 오른쪽 자식은 A [2*i + 1]이다. 힙은 힙 특성 유지하기(heapify), 힙 만들기(buildHeap), 삽입(insert), 삭제(delete)만 알면 된다. 힙 구현 힙 특성 유지하기(heapify) 배열 A에 대해 i번째 원소를 최대힙의 루트가 되게 한다. 아래는 퍼수도 코드이다. heapify(A, i){ l ..

2023.08.06