열혈 자료구조 - 9.2 힙의 구현과 우선순위 큐의 완성(1)

힙의 데이터 저장 과정

- 여기서 설명하는 힙은 데이터의 수가 작을수록 우선순위가 높은것으로 설정

- 데이터를 추가할때도 힙의 조건인 우선순위와 완전 이진트리라는 점을 깨면 안됨

- 오른쪽의 힙이 있을 때 데이터 3을 추가하는 경우

- 완전 이진트리로 구성하기 위해 우선 노드 8의 자식으로 들어감

    -> 하지만 지금은 우선순위의 조건에 맞지 않음

- 새 노드는 자리를 찾아가기 위해 부모노드와 비교해서 자리를 바꿈

 

힙의 데이터 삭제 과정

- 먼저 루트노드를 삭제하고 마지막 노드를 루트 노드로 이동

- 그리고 루트노드를 자식 노드와 비교해서 이동

    -> 비교할 때 자식노드 중 우선순위가 높은 자식이랑 자리를 바꿈

    -> 우선순위가 높은 자식이랑 바꾸면 다시 부모 노드는 자식 노드보다 우선 순위가 낮아지게 됨

 

삽입과 삭제의 과정에서 보이는 성능

- 배열 기반과 연결 리스트 기반의 힙의 성능

    -> 삽입 : O(n) 

        * 우선순위 비교를 하는데의 시간 복잡도

    -> 삭제 : O(1)

        * 단순히 맨 앞에 있는 데이터를 삭제하면 됨

- 힙 기반의 힙의 성능

    -> 삽입, 삭제 : $$O(log_2 n)$$