힙의 구현을 위해서는 데이터의 저장과 삭제의 방법을 먼저 알아야 한다.
최소 힙의 식은 다음과 같다.
“자식 노드 데이터의 우선순위 ≤ 부모 노드 데이터의 우선순위”
“새로운 데이터는 우선순위가 제일 낮다는 가정하에서 ‘마지막 위치’에 저장합니다. 그리고는 부모 노드와 우선순위를 비교해서 위치가 바뀌어야 한다면 바꿔줍니다. 바뀐다음에도 계속해서 부모 노드와 비교합니다. 제대로 된 위치를 찾을 때까지 말이지요”
데이터 저장과정과 비슷하게 힙에서 루트 노드를 삭제한후 제일 낮은 우선순위를 가진 노드를 루트로 옮긴후 heapify 과정을 거쳐준다.
출처: https://www.geeksforgeeks.org/introduction-to-min-heap-data-structure/
“우선순위 큐의 구현에 있어서 단순 배열이나 연결 리스트보다 힙이 더 적합한 이유는 어디에 있는가?”
답은 성능.
배열
연결 리스트